MediumArrayGraphTopological Sort

Sequence Reconstruction

1 approach, code in every language

You are given an integer array nums that is a permutation of the numbers from 1 to n. You are also given a collection of sequences, where each sequence is a list of integers drawn from those same values.

A valid supersequence is any ordering of the numbers 1 through n such that every given sequence appears within it as a subsequence, meaning its elements occur in the same relative order though not necessarily adjacent.

Determine whether nums is the one and only sequence that can be reconstructed as the shortest supersequence of all the given sequences. Return true if nums is uniquely reconstructable, and false otherwise.

Example 1

Input: nums = [1,2,3], sequences = [[1,2],[1,3]]

Output: false

We know 1 comes before both 2 and 3, but the order of 2 and 3 is unconstrained, so both [1,2,3] and [1,3,2] are valid; the reconstruction is not unique.

Example 2

Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]

Output: true

The edges force 1 before 2, 1 before 3, and 2 before 3, which pins the order to exactly [1,2,3].

Constraints

n == nums.length
1 <= n <= 10^4
nums is a permutation of the integers from 1 to n.
1 <= sequences.length <= 10^4
1 <= sum of sequences[i].length <= 10^5
1 <= sequences[i][j] <= n

Kahn's Topological Sort with Uniqueness Check

Build a precedence graph from the sequences and confirm a single node is free at every step while matching nums.

Loading animation…

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

1Initialize an empty adjacency set and a zero in-degree for every value in nums.
2For each sequence add an edge between every pair of consecutive elements, incrementing in-degree only for edges that are not already present.
3Run Kahn's algorithm, but before removing a node verify the queue holds exactly one candidate; more than one means the ordering is ambiguous.
4Check that each dequeued node equals the next expected value in nums; a mismatch means nums is not the reconstruction.
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

Time

O(V + E)

Space

O(V + E)

V is the number of values in nums and E is the total length of all sequences.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Is the Running Order Forced is our own problem on the technique behind Sequence Reconstruction: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free