Domain 2MediumCORE

Sequence Reconstruction

We are given a target permutation org (containing numbers 1 to n) and a list of subsequences seqs. We need to determine if there is exactly one valid sequence that satisfies all the ordering constraints provided in seqs, and if that unique sequence matches org exactly.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Graph#Topological Sort

444. Sequence Reconstruction

Model: qwen3.5:9b
Topics: Graph,Topological Sort
FAANG asked: 1
Acceptance rate: 23.7%


Problem Breakdown

We are given a target permutation org (containing numbers 1 to n) and a list of subsequences seqs. We need to determine if there is exactly one valid sequence that satisfies all the ordering constraints provided in seqs, and if that unique sequence matches org exactly.

Key inputs:

  • org: The target permutation (e.g., [1, 2, 3]).
  • seqs: A list of lists representing subsequences (e.g., [[1, 2], [1, 3]]).

Implicit constraints & tricky cases:

  • Uniqueness: If there are multiple valid topological orderings consistent with the edges in seqs, we return false. This happens if at any point during reconstruction, we have a choice of which element to pick next (multiple nodes with zero incoming dependencies).
  • Completeness: Every number present in org must be accounted for by the constraints in seqs. If an element from org is missing entirely or its relative order isn’t strictly defined against others, ambiguity arises.
  • Graph Construction: Each pair [u, v] inside a sequence implies a directed edge u→vu \to v (meaning u must come before v).

Intuition

This problem maps directly to finding the unique topological sort of a Directed Acyclic Graph (DAG) constructed from seqs.

  1. Brute Force: We could try generating all permutations and checking if they satisfy every subsequence in seqs, then see which one matches org uniquely. This is O(n!)O(n!), which will time out for n=104n=10^4.
  2. Graph Approach: Instead of guessing orders, we build a graph where nodes are numbers and edges represent “must come before” relationships from seqs.
  3. Uniqueness Condition: A topological sort is unique if and only if at every step of the sorting process (Kahn’s Algorithm), there is exactly one node with an in-degree of zero available to be added to our result sequence. If we ever have two or more such nodes, it means their relative order isn’t constrained by seqs, leading to multiple valid reconstructions -> return false immediately.
  4. Validation: After constructing the unique sort (if possible), we must verify that this resulting list is identical element-by-element with org.

Approach

  1. Graph Construction: Iterate through each sequence in seqs and build an adjacency list (adj) where u -> v means u precedes v. Simultaneously, calculate the in-degree for every node encountered.
  2. Node Validation: Ensure that all numbers present in org are actually part of our graph (i.e., they appear as keys or values). If a number from org is missing entirely, we can’t reconstruct it -> return false. Note: We should only track nodes relevant to the permutation range defined by org.
  3. Topological Sort with Uniqueness Check: Use Kahn’s Algorithm (BFS-based):
    • Initialize a queue with all nodes having an in-degree of 0.
    • While the queue is not empty:
      • If there are more than one node in the queue, it implies ambiguity -> return false immediately.
      • Pop the single node u, append to our reconstructed list.
      • For each neighbor v of u: decrement its in-degree; if 0, add to queue.
  4. Final Comparison: If we successfully process all nodes without hitting ambiguity and the length matches org, compare the resulting sequence with org. They must be identical for a true result (though strictly speaking, uniqueness + matching edges usually implies equality).

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E) where NN is the number of elements in seqs and EE is the total length of all sequences. We iterate through each sequence once to build the graph (O(E)O(E)) and then traverse nodes/edges exactly once during Kahn’s algorithm (O(V+E)O(V+E)).
  • Space Complexity: O(N+E)O(N + E) for storing the adjacency list, in-degree map, and queue.

Solution

from collections import defaultdict, deque
from typing import List

class Solution:
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        # 1. Build Graph & In-Degree Map
        adj = defaultdict(list)
        in_degree = {}
        
        # Initialize nodes from 'org' to ensure we track all required elements
        for num in org:
            if num not in in_degree:
                in_degree[num] = 0
        
        # Populate edges and degrees based on seqs
        for path in seqs:
            for i in range(len(path) - 1):
                u, v = path[i], path[i+1]
                
                # Only add edge if both nodes are within the valid permutation scope (optional but safe)
                # However, strictly we must ensure all 'org' elements exist. 
                # If seqs contains numbers not in org, they shouldn't affect reconstruction of org uniquely?
                # Standard logic: Build graph from edges provided by seqs.
                
                if v not in adj[u]:  # Avoid duplicate edges for same pair (though problem implies unique)
                    adj[u].append(v)
                    
                # Ensure nodes are tracked; handle potential missing keys gracefully
                if u not in in_degree: 
                     in_degree[u] = 0
                if v not in in_degree:
                     in_degree[v] = 1
                
        # Check for completeness: Every element in 'org' must be present as a node.
        # If seqs defines edges that create nodes outside of org, we might have issues? 
        # The problem implies reconstruction OF org. Any number not in org is invalid context usually.
        
        if len(in_degree) != len(org):
            return False
            
        # 2. Kahn's Algorithm with Uniqueness Check
        queue = deque()
        for node, degree in in_degree.items():
            if degree == 0:
                queue.append(node)
                
        reconstructed = []
        
        while queue:
            # If more than one candidate exists at this step -> Ambiguity (Not Unique)
            if len(queue) > 1:
                return False
            
            u = queue.popleft()
            reconstructed.append(u)
            
            for v in adj[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
                    
        # If we processed fewer nodes than org length, something was disconnected or missing. 
        # But since we checked len(in_degree), this should align unless logic above missed initialization.
        
        return reconstructed == org

Edge Cases Handled

  • Ambiguity: The code returns False immediately if the queue contains more than one element at any step, ensuring only a unique topological sort is accepted.
  • Missing Elements: If an integer in org does not appear as a key or value during graph construction (or isn’t reachable), it won’t be visited by Kahn’s algorithm correctly relative to its count; the length check ensures we reconstruct exactly what was provided.
  • Empty Sequences/Graphs: The loop over seqs handles empty lists gracefully, but if org has elements and no edges define them (e.g., disjoint nodes), they might end up with in-degree 0 initially. If multiple such nodes exist simultaneously, the queue size check catches it as non-unique.
  • Disconnected Components: Any number in org that isn’t part of a connected component defined by seqs will create ambiguity if there are other zero-indegree components available at the same time step (caught by len(queue) > 1).