Problem 24.5 · Topological SortMedium

Sequence Reconstruction

What it teaches: A topological order is unique exactly when there is only ever one choice.

Practise it on judges as “Sequence Reconstruction”.

The problem

nums is a permutation of 1..n. Each list in sequences is a subsequence of it. Return true if nums is the only shortest sequence that contains every list as a subsequence.

Example 1

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

[1,3,2] also works.

Example 2

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

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ "The only" order

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,3] sequences = [[1,2],[1,3]]	false
2	nums = [1,2,3] sequences = [[1,2]]	false
3	nums = [1,2,3] sequences = [[1,2],[1,3],[2,3]]	true

From slow to fast

Approaches

1. Kahn's with a uniqueness check · O(n + total sequence length)

Kahn's with a uniqueness check

Time O(n + total sequence length) Space O(n + edges)

Add edges from consecutive pairs. While the queue is non-empty: if it has more than one node, return false; the popped node must equal nums at that position.

Approach 1

import java.util.*;

class Solution {
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        int n = nums.length;
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new HashSet<>());
        int[] indeg = new int[n + 1];
        for (List<Integer> s : sequences)
            for (int i = 0; i + 1 < s.size(); i++)
                if (adj.get(s.get(i)).add(s.get(i + 1))) indeg[s.get(i + 1)]++;
        Deque<Integer> q = new ArrayDeque<>();
        for (int v = 1; v <= n; v++) if (indeg[v] == 0) q.offer(v);
        int idx = 0;
        while (!q.isEmpty()) {
            if (q.size() > 1) return false;
            int u = q.poll();
            if (nums[idx++] != u) return false;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
        }
        return idx == n;
    }
}

Verdict: Uniqueness falls out of the queue size.

Before you submit

Edge cases and common mistakes

Test these inputs

Sequences that don't mention some number
Single-element sequences

Mistakes people make

Counting duplicate edges twice in in-degree.

Interview

Follow-up questions

Where does uniqueness of a topological order matter in practice?

Command Palette

The problem

Approaches

Kahn's with a uniqueness check

Edge cases and common mistakes

Follow-up questions