Sequence Reconstruction (Unique Topo Order)

📋

Problem

Imagine you have a secret recipe that can only be reconstructed if all the steps are uniquely ordered. Given partial sequences of steps, can you determine if the original recipe order is uniquely reconstructible?

Given an original sequence org of integers from 1 to n, and a list of sequences seqs, each sequence is a subsequence of the original sequence. Determine if org is the only sequence that can be reconstructed from seqs. Reconstruction means building a shortest common supersequence of the sequences in seqs. Return true if and only if it is possible to reconstruct the original sequence uniquely.

1 ≤ n ≤ 10^5seqs contains sequences with elements in [1, n]Total length of all sequences in seqs does not exceed 10^5

Edge cases: seqs is empty → falseseqs contains sequences with elements not in org → falseorg is length 1 and seqs contains [[1]] → true

</>

IDE

def sequenceReconstruction(org: list[int], seqs: list[list[int]]) -> bool:public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs)bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs)function sequenceReconstruction(org, seqs)

def sequenceReconstruction(org, seqs):
    # Write your solution here
    pass

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    // Write your solution here
    return false;
}

function sequenceReconstruction(org, seqs) {
    // Write your solution here
    return false;
}

Common Bugs to Avoid

Wrong: trueFailed to detect multiple valid topological orders; uniqueness check missing.✅ Add check that at each step only one node has zero in-degree before choosing it.

Wrong: trueDid not detect cycle in graph, incorrectly assuming valid reconstruction.✅ Implement cycle detection in DFS or BFS and return false if cycle found.

Wrong: trueDid not validate that all elements in seqs are within org's range.✅ Check all elements in seqs against org's valid range before processing.

Wrong: falseIncorrectly rejected valid unique reconstruction due to improper uniqueness check.✅ Ensure that the reconstructed sequence matches org exactly and uniqueness is enforced.

Wrong: trueReturned true when seqs is empty, ignoring lack of information.✅ Return false immediately if seqs is empty or contains no sequences.

✓

Test Cases

Make sure your solution handles empty and minimal inputs correctly before proceeding.

Focus on detecting cycles and enforcing uniqueness in your topological sort.

Optimize your solution to linear time complexity using graph traversal techniques.

t1_01basic

Input{"org":[1,2,3],"seqs":[[1,2],[1,3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Both [1,2,3] and [1,3,2] are valid supersequences, so unique reconstruction is not possible.

💡 Consider how multiple valid topological orders can exist.

💡 Check if the graph constructed from seqs has more than one valid topological order.

💡 Ensure uniqueness by verifying that at each step only one node has zero in-degree.

Why it failed: Returned true incorrectly - failed to detect multiple valid topological orders. Fix by checking uniqueness of zero in-degree nodes at each step.

✓ Correctly identified multiple valid reconstructions; uniqueness check implemented.

t1_02basic

Input{"org":[1,2,3],"seqs":[[1,2],[2,3]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Only one valid topological order [1,2,3] matches org, so unique reconstruction is possible.

💡 Build the graph and track in-degree counts carefully.

💡 Use topological sort and verify that only one node is available to pick at each step.

💡 Confirm that the reconstructed sequence matches org exactly.

Why it failed: Returned false incorrectly - failed to confirm unique reconstruction. Fix by ensuring the reconstructed sequence matches org and uniqueness is enforced.

✓ Correctly confirmed unique reconstruction matching org.

t2_01edge

Input{"org":[1],"seqs":[]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty seqs means no information to reconstruct org, so return false.

💡 Check behavior when seqs is empty or contains no sequences.

💡 If no sequences are given, reconstruction is impossible.

💡 Return false immediately if seqs is empty.

Why it failed: Returned true incorrectly - did not handle empty seqs input. Fix by returning false when seqs is empty.

✓ Correctly returned false for empty seqs input.

t2_02edge

Input{"org":[1],"seqs":[[1]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single element org and seqs containing that element means unique reconstruction is trivially true.

💡 Consider the simplest case with one element in org and seqs.

💡 Check if seqs contains the single element matching org.

💡 Return true if seqs fully covers org with one element.

Why it failed: Returned false incorrectly - failed to handle single element org with matching seqs. Fix by checking coverage of all elements in org.

✓ Correctly returned true for single element org with matching seqs.

t2_03edge

Input{"org":[1,2],"seqs":[[1,3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

seqs contains element 3 not in org, so reconstruction is invalid and must return false.

💡 Validate that all elements in seqs are within the range of org.

💡 If seqs contains elements outside org, reconstruction is impossible.

💡 Return false if any element in seqs is not in org.

Why it failed: Returned true incorrectly - did not validate elements in seqs against org. Fix by checking element validity before reconstruction.

✓ Correctly returned false when seqs contains invalid elements.

t3_01corner

Input{"org":[1,2,3],"seqs":[[1,2],[2,3],[1,3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Multiple valid topological orders exist due to extra edge [1,3], so unique reconstruction is false.

💡 Check if extra edges create multiple valid orders.

💡 A greedy approach picking any zero in-degree node may fail here.

💡 Ensure uniqueness by verifying only one zero in-degree node at each step.

Why it failed: Returned true incorrectly - greedy approach failed to detect multiple valid orders. Fix by enforcing uniqueness check on zero in-degree nodes.

✓ Correctly detected multiple valid orders and returned false.

t3_02corner

Input{"org":[1,2,3],"seqs":[[1,2],[2,3],[3,1]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Cycle exists in seqs graph (3->1), so no valid topological order; reconstruction false.

💡 Detect cycles in the graph to invalidate reconstruction.

💡 DFS with cycle detection or in-degree count can find cycles.

💡 Return false if cycle detected.

Why it failed: Returned true incorrectly - failed to detect cycle in graph. Fix by adding cycle detection in DFS or BFS.

✓ Correctly detected cycle and returned false.

t3_03corner

Input{"org":[1,2,3,4],"seqs":[[1,2],[2,3],[3,4],[1,3]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Despite extra edge [1,3], only one valid topological order matches org, so unique reconstruction is true.

💡 Check if extra edges do not create ambiguity in order.

💡 Verify that only one node has zero in-degree at each step.

💡 Confirm reconstructed sequence matches org exactly.

Why it failed: Returned false incorrectly - failed to recognize unique reconstruction despite extra edges. Fix by verifying uniqueness at each step and matching org.

✓ Correctly confirmed unique reconstruction despite extra edges.

t4_01performance

Input{"org":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"seqs":[]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n+m) complexity required; brute force O(n!) will TLE.

💡 Use graph construction and topological sort with uniqueness check.

💡 Avoid brute force permutations; use DFS or BFS with in-degree counts.

💡 Ensure O(n+m) time complexity to pass large inputs.

Why it failed: TLE due to brute force permutation approach; fix by implementing O(n+m) graph-based topological sort with uniqueness check.

✓ Efficient O(n+m) solution confirmed by passing performance test.

Practice

1. 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

2. You are given n courses labeled from 1 to n and a list of prerequisite pairs where each pair [a, b] means you must take course a before course b. You want to find the minimum number of semesters needed to complete all courses if you can take any number of courses in parallel as long as their prerequisites are met. Which algorithmic approach guarantees finding the minimum semesters efficiently?

easy

A. Use dynamic programming to try all subsets of courses and pick the minimal semester count.

B. Use a greedy approach that always picks the course with the fewest prerequisites next.

C. Use a topological sort with BFS (Kahn's Algorithm) to process courses level by level based on in-degree zero nodes.

D. Use depth-first search (DFS) to detect cycles and then schedule courses in reverse postorder.

Solution

1. Step 1: Understand the problem constraints

   The problem requires scheduling courses respecting prerequisites and minimizing semesters, allowing parallel courses per semester.

2. Step 2: Identify the suitable algorithm

   Kahn's Algorithm (topological sort with BFS) processes nodes with zero in-degree in batches (levels), naturally modeling semesters and ensuring minimal semesters.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Level-by-level BFS matches semesters needed [OK]

Hint: Minimum semesters = levels in topological BFS [OK]

Common Mistakes:

• Thinking greedy picking minimal prerequisites works
• Confusing DFS order with minimal semester scheduling
• Trying exponential DP without pruning

3. What is the worst-case time complexity of the iterative DFS approach that enumerates all paths from source to target in a DAG with n nodes, where the number of paths can be exponential?

medium

A. O(n * 2^n) accounting for path copying and stack operations

B. O(2^n) due to exponential number of paths in worst case

C. O(n!) because permutations of nodes are explored

D. O(n^2) due to visiting each edge once

Solution

1. Step 1: Identify number of paths

   In worst case, number of paths can be exponential, roughly 2^n for DAGs with branching.

2. Step 2: Analyze per-path cost

   Each path is stored and copied when pushed to stack, costing O(n) per path. Total time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Exponential paths times linear path length copying [OK]

Hint: Exponential paths x linear path copying = O(n * 2^n) [OK]

Common Mistakes:

• Ignoring path copying cost
• Confusing edge visits with path enumeration

4. Suppose the problem is modified so that edges can be dynamically added or removed, and you need to repeatedly query which nodes are eventually safe after each update. Which approach is best suited to efficiently handle these dynamic queries?

hard

A. Maintain in-degree counts and update them incrementally, adjusting the queue of safe nodes dynamically.

B. Use a DFS with memoization approach and invalidate memoization only for affected nodes after each update.

C. Re-run the entire reversed graph + Kahn's algorithm from scratch after each update.

D. Use a brute force DFS cycle detection from every node after each update.

Solution

1. Step 1: Understand dynamic graph updates

   Recomputing from scratch is expensive; brute force DFS is too slow for repeated queries.

2. Step 2: Incremental in-degree updates

   Maintaining in-degree counts and adjusting the queue of safe nodes incrementally allows efficient updates without full recomputation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incremental updates leverage Kahn's algorithm structure for dynamic graphs [OK]

Hint: Incremental in-degree updates enable efficient dynamic queries [OK]

Common Mistakes:

• Re-running full algorithm after each update
• Using brute force DFS repeatedly
• Invalidating all memoization unnecessarily

5. Suppose the problem is modified so that nodes can be revisited multiple times along a path (cycles allowed), and you want the largest color value on any path (possibly infinite). Which of the following approaches correctly handles this variant?

hard

A. Detect cycles and return -1 immediately since infinite paths exist

B. Use the original topological sort + DP approach, ignoring cycles

C. Use DFS with memoization and cycle detection to find maximum color counts on simple paths only

D. Apply Bellman-Ford style relaxation over multiple iterations to handle cycles and update color counts

Solution

1. Step 1: Understand impact of cycles

   Allowing cycles means paths can be infinitely long, so maximum color count can be unbounded.

2. Step 2: Recognize correct handling

   Detecting cycles and returning -1 is necessary to indicate no finite maximum exists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite paths imply no finite max color value; cycle detection is mandatory [OK]

Hint: Cycles imply infinite max color count [OK]

Common Mistakes:

• Trying to apply DP ignoring cycles or assuming memoized DFS suffices