Sequence Reconstruction
Medium · Graphs · Array · Graph · Topological Sort
Problem
You are given an integer array nums that is a permutation of 1 to n, and a list sequences in which every sequences[i] is a subsequence of nums.
A supersequence of sequences is a sequence that contains every sequences[i] as a subsequence. Return true if nums is the only shortest supersequence of sequences, and false if another shortest supersequence exists.
Put another way: read every pair of neighbors in every sequence as a rule "this number comes before that one". Return true exactly when those rules allow only one order of 1..n, which is then nums.
Examples
Input: nums = [2,1,3], sequences = [[2,1],[1,3]] Output: true
The rules say 2 before 1 and 1 before 3, which allows only 2, 1, 3.
Input: nums = [2,1,3], sequences = [[2,1],[2,3]] Output: false
2, 3, 1 also satisfies both rules, so nums is not the only one.
Input: nums = [1,2,3,4], sequences = [[1,2,3,4]] Output: true
The single sequence already fixes every position.
Constraints
- n == len(nums)
- 1 <= n <= 10^4
- nums is a permutation of 1..n
- 1 <= len(sequences) <= 10^4
- 1 <= len(sequences[i]) <= 10^4
- The total length of all sequences is at most 10^5
- Every sequences[i] is a subsequence of nums
Approaches
- Baseline: search the sequences for every neighboring pair of nums — time O(n · T), space O(1)
Follow-up
Can you see why it is enough to check that every neighboring pair of nums is an edge? If some pair nums[i], nums[i+1] is not, nothing forces their order and swapping them gives a second valid order. The use cases rebuild the order from scratch and ask which single positions are forced.
Related problems
Start free on Cariara · Coding problems · System design studio
