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 supersequence of all sequences. In other words:
Return true if nums is the unique shortest supersequence, or false otherwise.
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.
The insight: For nums to be the unique shortest supersequence, the topological sort of the sequences must produce exactly one valid ordering (nums itself). This happens when at every step, there is exactly one node with in-degree 0.
Real-world analogy: Imagine you have partial recordings of events and you want to reconstruct the exact timeline. If the partial recordings uniquely determine the order, there is exactly one valid reconstruction.
nums = [1,2,3], sequences = [[1,2],[1,3]]falsenums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]truenums = [4,1,5,2,6,3], sequences = [[5,2,6,3],[4,1,5,2]]truen == nums.length1 <= n <= 10^4nums is a permutation of all the integers in the range [1, n]1 <= sequences.length <= 10^41 <= sequences[i].length <= 10^41 <= sum(sequences[i].length) <= 10^51 <= sequences[i][j] <= nAll the arrays of sequences are uniquesequences[i] is a subsequence of numsClick "Run" to execute your code against test cases
Socratic guidance - I'll ask questions, not give answers