Sequence Reconstruction

Sequence Reconstruction medium

Description

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 if nums is the shortest possible and the only supersequence of all the subsequences in sequences. The shortest supersequence is a sequence of the minimum length that has every subsequence in sequences as a subsequence.

Return true if nums is the unique shortest supersequence for sequences, false otherwise.

Examples

> Case 1:
    nums = [1, 2, 3],  sequences = [[1, 2], [1, 3]]
    Output: false
    Explanation: both [1, 2, 3] and [1, 3, 2] are valid supersequences of the constraints.
 
> Case 2:
    nums = [1, 2, 3],  sequences = [[1, 2]]
    Output: false
 
> Case 3:
    nums = [1, 2, 3],  sequences = [[1, 2], [1, 3], [2, 3]]
    Output: true

Constraints

n == nums.length
1 <= n <= 10^4
nums is a permutation of all the integers in the range [1, n].

State design

Two questions to answer:

Is the topo order of the implied DAG equal to nums? (Does it agree?)
Is the topo order unique? (No other valid order exists?)

The “unique” check is the trick: a topo order is unique iff at every step of Kahn’s, the queue contains exactly one node. If the queue ever has 2+ zero-indegree nodes simultaneously, multiple valid orderings exist.

Try it yourself

⌨ Sequence Reconstruction — is nums the unique topo order?

def sequence_reconstruction(nums, sequences):
  # build the DAG from the subsequences; nums is the unique order iff Kahn's queue
  # never holds more than one node and the emitted order matches nums
  pass

Hint

Each adjacent pair in a sequence is an edge u -> v. Run Kahn's, but before emitting each node check the queue holds exactly one node (else the order is ambiguous) and that it equals the next element of nums.

Reveal solution

Code

The “queue size == 1” uniqueness check is the entire insight. A topo order is unique iff there’s no ambiguity at any step about which node to emit next. Kahn’s makes that explicit: if multiple eligible nodes are in the queue at once, ANY of them could be emitted, and a different choice would produce a different valid order. So we check size before each emission.

Analysis

Time: O(V + E) where E is the total length of all sequences.
Space: O(V + E).

Same skin

Alien Dictionary — different framing (characters from word ordering), same algorithmic core.
Course Schedule II — output the order (without uniqueness check).
Verifying a Topological Order — given a proposed order, check it’s valid (single pass, no topo sort).
Unique Number of Occurrences — different problem, related “uniqueness” feel.

Alien Dictionary Longest Increasing Path in a Matrix

Finished this page?