NeetCode #643LC-444MediumAdvanced Graphs
← Back to All Problems#643 · #444 · Sequence Reconstruction(序列重建)
📌 Problem Statement & Constraints
You are given an integer array
nums of length n and a list of sequences, each a subsequence of nums. Return true if nums is the shortest sequence that has all of sequences as subsequences, and false otherwise. Constraints: 1 <= n <= 10^4, 1 <= sequences.length <= 10^4.💡 Core Algorithmic Approaches
- The shortest common supersequence is unique exactly when the derived graph has a unique topological order.
- Build the graph from the adjacent pairs inside each sequence (they encode the relative order).
- Kahn's algorithm: if at any point the queue holds more than one node, the order is not unique.
- The resulting order must also equal
numsexactly.
💻 Benchmark Python3 Implementation
class Solution:
def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
from collections import defaultdict, deque
g = defaultdict(set) # sets avoid duplicate edges
indeg = {v: 0 for v in nums}
for seq in sequences:
for a, b in zip(seq, seq[1:]):
if b not in g[a]:
g[a].add(b)
indeg[b] += 1
q = deque(v for v in nums if indeg[v] == 0)
order = []
while q:
if len(q) > 1:
return False # more than one choice -> not unique
node = q.popleft()
order.append(node)
for nxt in g[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return order == nums # must reproduce the given sequence⚡ Complexity Deep Dive
⏱️ Time Complexity
O(total elements across sequences): each adjacency pair is processed once.
💾 Space Complexity
O(n) for the graph (at most 26 keys per position, but O(n) overall).
⚠️ Interview Pitfalls & Follow-ups
- Only checking the topological order: uniqueness also requires the queue to hold at most one node at every step.
- Adding duplicate edges: the in-degree would be inflated, breaking the sort.
- Forgetting that adjacent pairs are the only constraints: non-adjacent elements in a sequence imply order transitively.
- Not comparing with
nums: the unique order must match the given array.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.