Sequence Reconstruction

You are given an integer array nums of length n where nums is a permutation of the integers in the range [1, n]. You are also given a 2D integer array sequences where sequences[i] is a subsequence of nums.

Check whether the original sequence nums can be uniquely reconstructed from the sequences in sequences.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Return true if there is only one sequence that can be reconstructed from sequences and it is nums, otherwise return false.

Example 1:

Input: nums = [1,2,3], sequences = [[1,2],[1,3]] Output: false Explanation: There are two possible supersequences: [1,2,3] and [1,3,2]. The sequence [1,2] is a subsequence of both: [1,2,3] and [1,3,2]. The sequence [1,3] is a subsequence of both: [1,2,3] and [1,3,2]. Since nums is not the only shortest supersequence, we return false.

Example 2:

Input: nums = [1,2,3], sequences = [[1,2]] Output: false Explanation: The shortest possible supersequence is [1,2]. The sequence [1,2] is a subsequence of it: [1,2]. Since nums is not the shortest supersequence, we return false.

Example 3:

Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]] Output: true Explanation: The shortest possible supersequence is [1,2,3]. The sequence [1,2] is a subsequence of it: [1,2,3]. The sequence [1,3] is a subsequence of it: [1,2,3]. The sequence [2,3] is a subsequence of it: [1,2,3]. Since nums is the only shortest supersequence, we return true.

Constraints:

• n == nums.length
• 1 <= n <= 104
• nums is a permutation of the integers in the range [1, n].
• 1 <= sequences.length <= 104
• 1 <= sequences[i].length <= 104

Approach: Topological Sort Checking Uniqueness

Algorithm

1. Build a directed graph where each consecutive pair (a, b) inside a sequence becomes an edge a -> b
2. Compute indegrees and run BFS topological sort
3. The reconstruction is unique if and only if at every step there is exactly one node with indegree 0; if the queue ever holds more than one candidate, the order is not unique
4. If the topological order length is less than n (cycle) or the queue ever has size != 1, return false; otherwise true

Time & Space Complexity

• Time Complexity: O(n + m) - n nodes and m edges across all sequences
• Space Complexity: O(n + m) - the adjacency list and indegree array

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class SequenceReconstruction {

    /**
     * Check whether nums is the unique shortest supersequence of sequences.
     * @param nums Original permutation
     * @param sequences Given subsequences
     * @return true if nums can be uniquely reconstructed
     */
    public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
        int n = nums.length;
        int[] indegree = new int[n];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for (List<Integer> seq : sequences) {
            for (int i = 1; i < seq.size(); i++) {
                int a = seq.get(i - 1) - 1;
                int b = seq.get(i) - 1;
                if (a < 0 || a >= n || b < 0 || b >= n) {
                    return false;
                }
                graph.get(a).add(b);
                indegree[b]++;
            }
        }

        List<Integer> queue = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (queue.size() == 1) {
            int cur = queue.remove(0);
            order.add(cur);
            for (int next : graph.get(cur)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }

        return order.size() == n;
    }

    // Test method
    public static void main(String[] args) {
        SequenceReconstruction sr = new SequenceReconstruction();
        System.out.println("Input: nums = [1,2,3], sequences = [[1,2],[1,3]]");
        System.out.println("Output: " + sr.sequenceReconstruction(
                new int[]{1, 2, 3},
                List.of(List.of(1, 2), List.of(1, 3)))); // Expected: false

        System.out.println("Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]");
        System.out.println("Output: " + sr.sequenceReconstruction(
                new int[]{1, 2, 3},
                List.of(List.of(1, 2), List.of(1, 3), List.of(2, 3)))); // Expected: true
    }
}

Example Walkthrough

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

1. Edges: 1->2, 1->3. Indegrees: 1:0, 2:1, 3:1
2. Initial queue = {1} (size 1)
3. Pop 1; children 2 and 3 both reach indegree 0 -> queue = {2, 3} (size 2)
4. The while loop stops because the queue has more than one candidate
5. order.size() (1) != n (3) -> return false

For sequences = [[1,2],[1,3],[2,3]], the queue never has more than one entry, the order equals [1,2,3] -> true.

Key Points

1. Unique Topological Order: A topological order is unique iff at every step exactly one node has indegree 0
2. Queue Size Check: The while (queue.size() == 1) loop terminates early on ambiguity
3. Subsequence to Edges: Consecutive elements in each sequence define ordering constraints
4. Coverage: All n numbers must appear; missing values would produce fewer nodes
5. Cycle Case: If a cycle exists, the order length stays below n and the method returns false