Problem statement

https://leetcode.com/problems/sequence-reconstruction/

Solution

Original solution is supposed to be Topological sort: for example we topologically sort our nodes, and then find the longest path and check if it has length n-1, where $n$ is number of nodes, complexity is O(E + V).

However for this problem we do not need topological sort at all: first we check if set of all nodes in seqs is the same as org and if not, return False. Then we put all pairs of adjacent elements from seqs to defaultdict G. Finally, we iterate over org and check for each pair of adjacent elements it is inside our defaultdict. Also we need to check that we do not have edges in opposite direction, that is if index[x] >= index[y], we return False immedietly

Complexity

Time complexity is O(E + V), space complexity is O(E + V) as well.

Code

class Solution:
    def sequenceReconstruction(self, org, seqs):
        if set(org) != set(chain(*seqs)): return False
        index = {num: i for i, num in enumerate(org)}
        
        G = defaultdict(set)
        for seq in seqs:
            for x, y in zip(seq, seq[1:]):
                G[x].add(y)
                if index[x] >= index[y]: return False

        return all(y in G[x] for x, y in zip(org, org[1:]))