⚡Flashcard Drill➔
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

  1. The shortest common supersequence is unique exactly when the derived graph has a unique topological order.
  2. Build the graph from the adjacent pairs inside each sequence (they encode the relative order).
  3. Kahn's algorithm: if at any point the queue holds more than one node, the order is not unique.
  4. The resulting order must also equal nums exactly.

💻 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems