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
orgmust be accounted for by the constraints inseqs. If an element fromorgis 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 (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.
- Brute Force: We could try generating all permutations and checking if they satisfy every subsequence in
seqs, then see which one matchesorguniquely. This is , which will time out for . - Graph Approach: Instead of guessing orders, we build a graph where nodes are numbers and edges represent “must come before” relationships from
seqs. - 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. - Validation: After constructing the unique sort (if possible), we must verify that this resulting list is identical element-by-element with
org.
Approach
- Graph Construction: Iterate through each sequence in
seqsand build an adjacency list (adj) whereu -> vmeans u precedes v. Simultaneously, calculate the in-degree for every node encountered. - Node Validation: Ensure that all numbers present in
orgare actually part of our graph (i.e., they appear as keys or values). If a number fromorgis missing entirely, we can’t reconstruct it -> return false. Note: We should only track nodes relevant to the permutation range defined byorg. - 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
vofu: decrement its in-degree; if 0, add to queue.
- Final Comparison: If we successfully process all nodes without hitting ambiguity and the length matches
org, compare the resulting sequence withorg. They must be identical for a true result (though strictly speaking, uniqueness + matching edges usually implies equality).
Complexity Analysis
- Time Complexity: where is the number of elements in
seqsand is the total length of all sequences. We iterate through each sequence once to build the graph () and then traverse nodes/edges exactly once during Kahn’s algorithm (). - Space Complexity: 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
Falseimmediately 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
orgdoes 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
seqshandles empty lists gracefully, but iforghas 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
orgthat isn’t part of a connected component defined byseqswill create ambiguity if there are other zero-indegree components available at the same time step (caught bylen(queue) > 1).