Sequence Reconstruction (Unique Topo Order)

▶

Steps

setup

Initialize graph and nodes set

We start by extracting all unique nodes from the sequences and initializing an empty graph with no edges yet.

💡 Identifying all nodes upfront ensures we know the full set of elements to process and can detect missing elements early.

Line:

graph = defaultdict(set)
nodes = set()
for seq in seqs:
    for num in seq:
        nodes.add(num)

💡 The nodes set contains {1, 2, 3}, matching the original sequence elements.

setup

Validate nodes match original sequence

We check if the set of nodes from sequences matches the set of nodes in the original sequence.

💡 If nodes differ, reconstruction is impossible, so this early check can short-circuit the algorithm.

Line:

if nodes != set(org):
    return False

💡 All nodes required by org are present in seqs, so reconstruction is possible in principle.

setup

Build graph edges from sequences

For each sequence, add directed edges from each element to the next, representing ordering constraints.

💡 Edges encode the partial order that the topological sort must respect.

Line:

for seq in seqs:
    for i in range(len(seq) - 1):
        graph[seq[i]].add(seq[i+1])

💡 Edges added: 1->2 and 1->3, indicating 1 must come before 2 and 3.

traverse

Start DFS from node 1

Begin DFS traversal at node 1, marking it as processing to detect cycles.

💡 Marking nodes as processing helps detect cycles if we revisit them during recursion.

Line:

for node in org:
    if node not in visited:
        if not dfs(node):
            return False

💡 Node 1 state changes from unvisited to processing, starting recursion.

traverse

DFS explore edge 1->2

From node 1, we explore the edge to node 2, marking the edge as traversed and node 2 as processing.

💡 Exploring neighbors recursively builds the postorder stack and detects cycles.

Line:

for nei in graph[node]:
    if not dfs(nei):
        return False

💡 Edge 1->2 is a tree edge; node 2 is now processing.

traverse

DFS explore neighbors of node 2

Node 2 has no outgoing edges, so we mark it done and add it to the postorder stack.

💡 Nodes with no neighbors finish immediately, contributing to the topological order.

Line:

visited[node] = True
stack.append(node)

💡 Node 2 is fully processed and added to the stack.

traverse

DFS explore edge 1->3

Back at node 1, we explore the edge to node 3, marking it as traversed and node 3 as processing.

💡 Exploring all neighbors ensures the full graph is covered for topological order.

Line:

for nei in graph[node]:
    if not dfs(nei):
        return False

💡 Edge 1->3 is a tree edge; node 3 is now processing.

traverse

DFS explore neighbors of node 3

Node 3 has no outgoing edges, so we mark it done and add it to the postorder stack.

💡 Finishing node 3 adds it to the topological order stack.

Line:

visited[node] = True
stack.append(node)

💡 Node 3 is fully processed and added to the stack.

traverse

Finish processing node 1

All neighbors of node 1 are processed, so we mark node 1 done and add it to the stack.

💡 Completing node 1 finalizes the DFS postorder for this branch.

Line:

visited[node] = True
stack.append(node)

💡 Node 1 is fully processed and added last to the stack.

reconstruct

Reverse stack to get candidate order

We reverse the postorder stack to get a candidate topological order: [1,3,2].

💡 Reversing postorder gives a valid topological order of the graph.

Line:

stack.reverse()

💡 Candidate order differs from original order [1,2,3], indicating multiple valid orders.

compare

Check if candidate order matches original

We compare the candidate order [1,3,2] with the original sequence [1,2,3].

💡 If they differ, the reconstruction is not unique and must return false.

Line:

if stack != org:
    return False

💡 Multiple valid topological orders exist, so unique reconstruction fails.

import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

def sequenceReconstruction(org, seqs):
    graph = defaultdict(set)  # STEP 1
    nodes = set()  # STEP 1
    for seq in seqs:
        for num in seq:
            nodes.add(num)  # STEP 1
    if nodes != set(org):  # STEP 2
        return False
    for seq in seqs:
        for i in range(len(seq) - 1):
            graph[seq[i]].add(seq[i+1])  # STEP 3
    visited = {}
    stack = []
    def dfs(node):
        if node in visited:
            return visited[node]  # STEP 4
        visited[node] = False  # mark as processing (STEP 4)
        for nei in graph[node]:
            if not dfs(nei):  # STEP 5,7
                return False
        visited[node] = True  # mark as done (STEP 6,8,9)
        stack.append(node)  # STEP 6,8,9
        return True
    for node in org:
        if node not in visited:
            if not dfs(node):  # STEP 4
                return False
    stack.reverse()  # STEP 10
    if stack != org:  # STEP 11
        return False
    pos = {num: i for i, num in enumerate(org)}
    for u in graph:
        for v in graph[u]:
            if pos[u] >= pos[v]:
                return False
    return True

📊

Sequence Reconstruction (Unique Topo Order) - Watch the Algorithm Execute, Step by Step

Watching each step of the DFS traversal and how the algorithm detects cycles and uniqueness helps you understand the subtle conditions that make a topological order unique or ambiguous.

Visiting: none

1

2

3

Visiting: none

1

2

3

Visiting: none

1

2

3

Visiting: 1

1

2

3

Visiting: 2

Edge: 1 → 2

1

2

3

Visiting: 1

1

2

3

Queue / Stack

2

Visiting: 3

Edge: 1 → 3

1

2

3

Queue / Stack

2

Visiting: 1

1

2

3

Queue / Stack

23

Visiting: none

1

2

3

Queue / Stack

231

Visiting: none

1

2

3

Queue / Stack

132

Visiting: none

1

2

3

Queue / Stack

132

Key Takeaways

✓ DFS postorder traversal produces a valid topological order by finishing nodes after all descendants.

This is hard to see from code alone because the recursion stack and node states are implicit; visualization shows the exact order nodes finish.

✓ Multiple valid topological orders can exist if the graph has branching edges, causing reconstruction to be non-unique.

Seeing the candidate order differ from the original sequence reveals why uniqueness fails, which is subtle without visualizing the stack reversal.

✓ Cycle detection via node states (processing vs done) prevents infinite recursion and invalid orders.

Understanding how marking nodes as processing helps detect cycles is clearer when watching node state changes step-by-step.

Practice

1. You are given an undirected tree with n nodes. The task is to find all nodes that, when chosen as roots, produce trees with minimum height. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Iteratively remove leaf nodes layer by layer until 1 or 2 centroids remain.

B. Use dynamic programming to store subtree heights and combine results.

C. Run BFS/DFS from every node to calculate tree height and pick minimum roots.

D. Apply a greedy approach by always choosing the node with maximum degree as root.

Solution

1. Step 1: Understand the problem structure

   The problem asks for nodes that minimize tree height when chosen as roots. This corresponds to finding centroids of the tree.

2. Step 2: Identify the correct approach

   Iteratively trimming leaves (nodes with degree 1) layer by layer reduces the tree towards its centroids. This approach guarantees finding the minimum height roots efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Leaf trimming is the known optimal pattern for Minimum Height Trees [OK]

Hint: Leaf trimming finds centroids efficiently [OK]

Common Mistakes:

• Thinking BFS from each node is efficient
• Confusing DP with leaf trimming
• Greedy max-degree node is incorrect

2. Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?

easy

A. [3]

B. [0, 2, 3]

C. [2]

D. [1]

Solution

1. Step 1: Initialize graph and degrees

   Nodes: 0,1,2,3; edges connect 1 to 0,2,3. Degrees: 0->1, 1->3, 2->1, 3->1. Leaves initially: [0,2,3].

2. Step 2: Trim leaves until ≤ 2 nodes remain

   Remove leaves [0,2,3], decrement neighbors' degrees. Node 1 degree reduces from 3 to 0, becomes leaf. Remaining nodes = 4 - 3 = 1. Loop ends. Return [1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only node 1 remains as centroid after trimming [OK]

Hint: Leaves trimmed until ≤2 nodes remain [OK]

Common Mistakes:

• Returning initial leaves
• Off-by-one in loop
• Not updating degrees correctly

3. Consider the following buggy code snippet for topological sort positions. Which line contains the subtle bug that can cause incorrect matrix construction?

medium

A. Line where graph[u].append(v) is called

B. Line where queue is initialized with nodes of zero in-degree

C. Line where pos[node] is assigned idx

D. Line where in_degree[u] is incremented instead of in_degree[v]

Solution

1. Step 1: Identify how in-degree is updated

   In-degree should count incoming edges; incrementing in_degree[u] is incorrect because u is the source, not the target.

2. Step 2: Understand impact of bug

   Incorrect in-degree counts cause wrong zero in-degree nodes, breaking topological order and matrix correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct in-degree update is critical for cycle detection and ordering [OK]

Hint: In-degree counts incoming edges, not outgoing [OK]

Common Mistakes:

• Mixing source and target when updating in-degree
• Assuming graph edges are undirected

4. What is the time complexity of the optimal algorithm that uses topological sort combined with iterative DP to find the largest color value in a directed graph with n nodes and e edges?

medium

A. O(n * 26 * e) due to nested loops over edges and colors

B. O(n^2) since DP updates require comparing all pairs of nodes

C. O(n + e) ignoring the 26 colors dimension as constant

D. O((n + e) * 26) because each node and edge is processed once with 26 color updates

Solution

1. Step 1: Identify main loops

   Topological sort processes each node and edge once, so base complexity is O(n + e).

2. Step 2: Account for DP color dimension

   For each node and edge, 26 colors are updated, multiplying complexity by 26.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Complexity is O((n + e) * 26), which is linear in graph size with constant color factor [OK]

Hint: Remember DP color dimension multiplies base graph traversal [OK]

Common Mistakes:

• Ignoring 26 colors or assuming quadratic complexity

5. What is the time complexity of the optimal BFS-based topological sort algorithm for the Parallel Courses problem, given n courses and m prerequisite relations?

medium

A. O(n + m) because each node and edge is processed once in BFS

B. O(m^2) because updating indegrees requires scanning all edges repeatedly

C. O(n * m) because for each course you process all edges

D. O(n^2) because in the worst case all courses depend on all others

Solution

1. Step 1: Analyze graph traversal

   Each course (node) is enqueued and dequeued at most once; each edge is visited once when decrementing indegree.

2. Step 2: Combine node and edge processing

   Total operations proportional to number of nodes plus edges -> O(n + m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in nodes and edges [OK]

Hint: Each edge and node processed once in BFS [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing indegree updates as repeated scans
• Assuming dense graph means O(n^2) always