Sequence Reconstruction

Intuition

Each sequence tells us the relative order of its consecutive elements, so consecutive pairs become directed edges in a precedence graph. Reconstructing the original order is exactly a topological sort of that graph. The order is unique precisely when the sort never has a choice: at every step exactly one node has in-degree zero. If two or more nodes are simultaneously free, more than one valid ordering exists, and if zero are free before finishing, there is a cycle. Finally, the single ordering that is produced must match nums element by element.

Algorithm walkthrough

1. 1Initialize an empty adjacency set and a zero in-degree for every value in nums.
2. 2For each sequence add an edge between every pair of consecutive elements, incrementing in-degree only for edges that are not already present.
3. 3Run Kahn's algorithm, but before removing a node verify the queue holds exactly one candidate; more than one means the ordering is ambiguous.
4. 4Check that each dequeued node equals the next expected value in nums; a mismatch means nums is not the reconstruction.
5. 5If the process consumes all n values with a unique choice at each step, return true; otherwise return false.

Implementation

from collections import deque, defaultdict
from typing import List

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        adj = defaultdict(set)
        indegree = {x: 0 for x in nums}

        for seq in sequences:
            for i in range(len(seq) - 1):
                u, v = seq[i], seq[i + 1]
                if v not in adj[u]:
                    adj[u].add(v)
                    indegree[v] += 1

        queue = deque([x for x in nums if indegree[x] == 0])
        index = 0
        while queue:
            if len(queue) > 1:
                return False
            node = queue.popleft()
            if index >= n or node != nums[index]:
                return False
            index += 1
            for nxt in adj[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return index == n