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. You are given a list of words sorted lexicographically in an unknown language. Your task is to determine the order of characters in this alien language. Which algorithmic approach guarantees an optimal solution to infer the character order from these constraints?

easy

A. Topological sort on a directed graph constructed from character precedence relations inferred from adjacent words

B. Greedy algorithm that picks the first differing character between adjacent words and orders them immediately

C. Dynamic programming to find the longest common subsequence between all pairs of words

D. Brute force comparison of all pairs of words to deduce character order by frequency

Solution

1. Step 1: Understand problem constraints

   The problem requires inferring a partial order of characters based on lexicographical ordering of words, which naturally forms a directed graph of precedence relations.

2. Step 2: Identify suitable algorithm

   Topological sort is the standard algorithm to find a linear order of nodes in a directed acyclic graph (DAG), which fits perfectly to infer character order from precedence edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort handles partial orders and cycles correctly [OK]

Hint: Partial order inference -> topological sort [OK]

Common Mistakes:

• Assuming greedy approach works without cycle detection
• Confusing longest common subsequence with order inference
• Using brute force frequency counts which ignore order

2. You are given a directed graph where each node represents a state, and edges represent transitions. Some states lead to cycles, while others eventually lead to terminal states with no outgoing edges. Which algorithmic approach guarantees finding all states that are "eventually safe" (i.e., cannot reach any cycle) in an efficient manner?

easy

A. Use a greedy approach to repeatedly remove nodes with no outgoing edges until no nodes remain.

B. Construct the reverse graph and apply Kahn's algorithm (topological sort using in-degree) to identify safe nodes.

C. Apply dynamic programming with memoization on node states to mark safe and unsafe nodes.

D. Perform a brute force DFS from each node to detect cycles and mark safe nodes accordingly.

Solution

1. Step 1: Understand problem requirements

   The problem requires identifying nodes that cannot reach any cycle, i.e., nodes that eventually lead to terminal nodes.

2. Step 2: Recognize optimal approach

   Reversing the graph and applying Kahn's algorithm on in-degree allows us to efficiently find all nodes that lead to terminal nodes by processing nodes with zero out-degree in the original graph.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reverse graph + Kahn's algorithm is the known optimal solution for eventual safe states [OK]

Hint: Reverse graph + Kahn's algorithm finds safe nodes efficiently [OK]

Common Mistakes:

• Confusing brute force DFS with optimal topological approach
• Assuming greedy removal without reversing graph suffices
• Misapplying DP without graph reversal

3. What is the time complexity of Kahn's Algorithm for finding a topological order in a graph with V vertices and E edges?

medium

A. O(V * E) because each vertex processes all edges repeatedly.

B. O(V^2) because in-degree updates require scanning all vertices.

C. O(V + E) because each vertex and edge is processed exactly once.

D. O(E log V) due to priority queue operations for ordering.

Solution

1. Step 1: Identify operations on vertices and edges

   Each vertex is enqueued and dequeued once; each edge is visited once to decrement in-degree.

2. Step 2: Sum total work

   Processing all vertices and edges once leads to O(V + E) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time in graph size is standard for BFS topological sort [OK]

Hint: Each edge and vertex processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing in-degree updates as scanning all vertices
• Thinking priority queues are used by default

4. The following code attempts to compute the minimum semesters to complete all courses using BFS topological sort. Identify the bug that causes incorrect results or infinite loops.

from collections import deque, defaultdict

def min_semesters_buggy(n, relations):
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    for u, v in relations:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    semester = 0
    processed = 0

    while queue:
        semester += 1
        course = queue.popleft()  # Bug here: processing one course per semester
        processed += 1
        for nei in graph[course]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    return semester if processed == n else -1

medium

A. Line with 'semester += 1' increments semester too early.

B. Line with 'course = queue.popleft()' processes only one course per semester instead of all available.

C. Line with 'indegree[nei] -= 1' incorrectly decrements indegree causing negative values.

D. Line with 'queue = deque(...)' initializes queue incorrectly missing some zero indegree courses.

Solution

1. Step 1: Identify how courses are processed per semester

   The code processes only one course per semester by popping one element from the queue.

2. Step 2: Understand impact on semester count

   Since multiple courses with zero indegree can be taken in parallel, processing one at a time inflates semester count incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct BFS processes all zero indegree nodes per semester [OK]

Hint: Process all zero indegree courses per semester, not one [OK]

Common Mistakes:

• Incrementing semester inside inner loop
• Not processing all available courses in one semester
• Incorrect indegree updates causing infinite loops

5. Suppose the problem is modified so that some courses can be taken multiple times (repeatedly) and prerequisites must be satisfied each time before retaking. Which of the following statements about adapting the BFS topological sort approach is correct?

hard

A. We should switch to a dynamic programming approach because BFS topological sort cannot handle repeated courses.

B. The original BFS topological sort can be used without changes since it handles cycles by returning -1.

C. We can use BFS topological sort by resetting indegrees after each semester and reprocessing courses as needed.

D. The problem becomes invalid because repeated courses create cycles; BFS topological sort cannot be applied directly.

Solution

1. Step 1: Understand repeated courses and prerequisites

   Allowing repeated courses with prerequisites means cycles can form because a course depends on itself indirectly.

2. Step 2: Analyze BFS topological sort applicability

   BFS topological sort requires a DAG; cycles break this assumption, so it cannot be applied directly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Repeated courses induce cycles -> BFS topological sort invalid [OK]

Hint: Repeated courses create cycles, breaking DAG assumption [OK]

Common Mistakes:

• Assuming BFS topological sort handles cycles by returning -1
• Thinking resetting indegrees can simulate repeats correctly
• Believing DP is always needed without analyzing graph structure