Sequence Reconstruction (Unique Topo Order)

🎯

Sequence Reconstruction (Unique Topo Order)

mediumGRAPHAmazonGoogle

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?

💡 This problem asks if a unique topological order exists given partial orderings. Beginners often struggle because it combines graph construction, cycle detection, and uniqueness checks, which are not trivial to integrate.

📋

Problem Statement

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

💡

Example

Input"org = [1,2,3], seqs = [[1,2],[1,3]]"

Outputfalse

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

Input"org = [1,2,3], seqs = [[1,2],[2,3]]"

Outputtrue

Only [1,2,3] can be reconstructed from seqs, so unique reconstruction is possible.

• seqs is empty → false
• seqs contains sequences with elements not in org → false
• org is length 1 and seqs contains [[1]] → true
• seqs contains duplicate sequences → should not affect correctness

⚠️

Common Mistakes

Not checking if all nodes in org appear in seqs

Returns true incorrectly when seqs is missing elements

✅ Validate that nodes in seqs match exactly the nodes in org before processing

Not verifying uniqueness by checking queue size in BFS

May accept multiple valid sequences as unique

✅ At each BFS step, ensure only one node has zero in-degree

Ignoring cycle detection in DFS approach

Infinite recursion or incorrect results

✅ Use visited states to detect cycles and return false if found

Comparing topological order without reversing postorder in DFS

Order mismatch leads to false negatives

✅ Reverse the postorder stack before comparing with org

Not handling empty or invalid seqs input

Code may crash or return wrong result

✅ Add early checks for empty seqs or sequences with invalid elements

🧠

Brute Force (Check All Possible Supersequences)

💡 This approach tries to generate all possible sequences that can be formed from seqs and checks if org is the only one. It is impractical but helps understand the problem deeply.

Intuition

If we try to build all sequences that satisfy the subsequence constraints, we can check if only org matches. This brute force approach enumerates all possible sequences.

Algorithm

1. Generate all permutations of numbers from 1 to n.
2. For each permutation, check if all sequences in seqs are subsequences of it.
3. Count how many permutations satisfy the subsequence condition and match org.
4. Return true if exactly one permutation matches org, else false.

💡 This approach is conceptually simple but computationally infeasible for large n due to factorial permutations.

</>

Code

from itertools import permutations

def sequenceReconstruction(org, seqs):
    n = len(org)
    nums = list(range(1, n+1))
    count = 0
    for perm in permutations(nums):
        if all(is_subsequence(perm, seq) for seq in seqs):
            if list(perm) == org:
                count += 1
            if count > 1:
                return False
    return count == 1

def is_subsequence(seq, sub):
    it = iter(seq)
    return all(x in it for x in sub)

# Driver code
if __name__ == '__main__':
    org = [1,2,3]
    seqs = [[1,2],[1,3]]
    print(sequenceReconstruction(org, seqs))  # Expected: False

Line Notes

from itertools import permutationsImport permutations to generate all possible sequences

for perm in permutations(nums):Try every possible ordering of numbers 1 to n

if all(is_subsequence(perm, seq) for seq in seqs):Check if current permutation contains all seqs as subsequences

if count > 1:Early stop if more than one valid sequence found

import java.util.*;

public class Solution {
    public static boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        int n = org.length;
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) nums.add(i);
        int[] count = {0};
        permute(nums, 0, org, seqs, count);
        return count[0] == 1;
    }

    private static void permute(List<Integer> nums, int start, int[] org, List<List<Integer>> seqs, int[] count) {
        if (count[0] > 1) return;
        if (start == nums.size()) {
            if (allSubseq(nums, seqs)) {
                if (matchesOrg(nums, org)) count[0]++;
            }
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            Collections.swap(nums, start, i);
            permute(nums, start + 1, org, seqs, count);
            Collections.swap(nums, start, i);
        }
    }

    private static boolean allSubseq(List<Integer> perm, List<List<Integer>> seqs) {
        for (List<Integer> seq : seqs) {
            if (!isSubsequence(perm, seq)) return false;
        }
        return true;
    }

    private static boolean isSubsequence(List<Integer> perm, List<Integer> seq) {
        int i = 0, j = 0;
        while (i < perm.size() && j < seq.size()) {
            if (perm.get(i).equals(seq.get(j))) j++;
            i++;
        }
        return j == seq.size();
    }

    private static boolean matchesOrg(List<Integer> perm, int[] org) {
        for (int i = 0; i < org.length; i++) {
            if (!perm.get(i).equals(org[i])) return false;
        }
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        int[] org = {1,2,3};
        List<List<Integer>> seqs = Arrays.asList(Arrays.asList(1,2), Arrays.asList(1,3));
        System.out.println(sequenceReconstruction(org, seqs)); // Expected: false
    }
}

Line Notes

permute(nums, 0, org, seqs, count);Start generating all permutations from index 0

if (count[0] > 1) return;Stop early if more than one valid sequence found

if (allSubseq(nums, seqs)) {Check if current permutation contains all seqs as subsequences

if (matchesOrg(nums, org)) count[0]++;Increment count only if permutation matches original sequence

#include <bits/stdc++.h>
using namespace std;

bool isSubsequence(const vector<int>& perm, const vector<int>& seq) {
    int i = 0, j = 0;
    while (i < (int)perm.size() && j < (int)seq.size()) {
        if (perm[i] == seq[j]) j++;
        i++;
    }
    return j == (int)seq.size();
}

bool allSubseq(const vector<int>& perm, const vector<vector<int>>& seqs) {
    for (const auto& seq : seqs) {
        if (!isSubsequence(perm, seq)) return false;
    }
    return true;
}

bool matchesOrg(const vector<int>& perm, const vector<int>& org) {
    for (int i = 0; i < (int)org.size(); i++) {
        if (perm[i] != org[i]) return false;
    }
    return true;
}

void permute(vector<int>& nums, int start, const vector<int>& org, const vector<vector<int>>& seqs, int& count) {
    if (count > 1) return;
    if (start == (int)nums.size()) {
        if (allSubseq(nums, seqs) && matchesOrg(nums, org)) {
            count++;
        }
        return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, org, seqs, count);
        swap(nums[start], nums[i]);
    }
}

int main() {
    vector<int> org = {1,2,3};
    vector<vector<int>> seqs = {{1,2},{1,3}};
    vector<int> nums = {1,2,3};
    int count = 0;
    permute(nums, 0, org, seqs, count);
    cout << (count == 1 ? "true" : "false") << endl; // Expected: false
    return 0;
}

Line Notes

void permute(vector<int>& nums, int start, const vector<int>& org, const vector<vector<int>>& seqs, int& count)Recursive function to generate permutations

if (count > 1) return;Stop recursion early if more than one valid sequence found

if (allSubseq(nums, seqs) && matchesOrg(nums, org)) {Check if current permutation contains all seqs as subsequences and matches org

count++;Increment count for each valid permutation matching org

function isSubsequence(perm, seq) {
    let i = 0, j = 0;
    while (i < perm.length && j < seq.length) {
        if (perm[i] === seq[j]) j++;
        i++;
    }
    return j === seq.length;
}

function allSubseq(perm, seqs) {
    for (const seq of seqs) {
        if (!isSubsequence(perm, seq)) return false;
    }
    return true;
}

function matchesOrg(perm, org) {
    for (let i = 0; i < org.length; i++) {
        if (perm[i] !== org[i]) return false;
    }
    return true;
}

function permute(nums, start, org, seqs, count) {
    if (count.count > 1) return;
    if (start === nums.length) {
        if (allSubseq(nums, seqs) && matchesOrg(nums, org)) {
            count.count++;
        }
        return;
    }
    for (let i = start; i < nums.length; i++) {
        [nums[start], nums[i]] = [nums[i], nums[start]];
        permute(nums, start + 1, org, seqs, count);
        [nums[start], nums[i]] = [nums[i], nums[start]];
    }
}

// Driver code
const org = [1,2,3];
const seqs = [[1,2],[1,3]];
const nums = [1,2,3];
const count = {count: 0};
permute(nums, 0, org, seqs, count);
console.log(count.count === 1); // Expected: false

Line Notes

function permute(nums, start, org, seqs, count)Recursive function to generate all permutations

if (count.count > 1) return;Stop recursion early if more than one valid sequence found

if (allSubseq(nums, seqs) && matchesOrg(nums, org)) {Check if current permutation contains all seqs as subsequences and matches org

count.count++;Increment count for each valid permutation matching org

⏱

Complexity

TimeO(n! * m * k) where n is length of org, m is number of sequences, k average length of sequences

SpaceO(n) for permutation storage and recursion stack

We generate all permutations (n!) and check subsequences for each, which is very expensive.

💡 For n=10, n! is 3,628,800, which is too large to compute in reasonable time.

Interview Verdict: TLE

This approach is only useful to understand the problem and why we need better methods; it is not practical for interviews.

🧠

Graph Construction + BFS Topological Sort with Uniqueness Check

💡 This approach builds a graph from seqs and uses BFS topological sort to check if the order is unique and matches org. It is efficient and commonly accepted.

Intuition

If the graph has a unique topological order, then at every step there is exactly one node with zero in-degree. We verify this uniqueness and the order matches org.

Algorithm

1. Build a graph and compute in-degree for each node from seqs.
2. Initialize a queue with nodes having zero in-degree.
3. While queue is not empty, check if it contains exactly one node (uniqueness).
4. Pop the node, compare it with org at current index, decrement in-degree of neighbors.
5. If all nodes processed and order matches org, return true; else false.

💡 The key insight is checking the queue size at each step to ensure uniqueness of the next node in order.

</>

Code

from collections import deque, defaultdict

def sequenceReconstruction(org, seqs):
    if not seqs or not any(seqs):
        return False
    graph = defaultdict(set)
    in_degree = defaultdict(int)
    nodes = set()
    for seq in seqs:
        for num in seq:
            nodes.add(num)
    if nodes != set(org):
        return False
    for seq in seqs:
        for i in range(len(seq) - 1):
            if seq[i+1] not in graph[seq[i]]:
                graph[seq[i]].add(seq[i+1])
                in_degree[seq[i+1]] += 1
    queue = deque([node for node in org if in_degree[node] == 0])
    idx = 0
    while queue:
        if len(queue) > 1:
            return False
        current = queue.popleft()
        if org[idx] != current:
            return False
        idx += 1
        for nei in graph[current]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    return idx == len(org)

# Driver code
if __name__ == '__main__':
    org = [1,2,3]
    seqs = [[1,2],[2,3]]
    print(sequenceReconstruction(org, seqs))  # Expected: True

Line Notes

if not seqs or not any(seqs):Check for empty or invalid input early

nodes = set()Collect all unique nodes from seqs to validate input

if nodes != set(org):If nodes differ from org, reconstruction impossible

if len(queue) > 1:More than one node with zero in-degree means multiple valid orders

import java.util.*;

public class Solution {
    public static boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        if (seqs == null || seqs.isEmpty()) return false;
        Set<Integer> nodes = new HashSet<>();
        for (List<Integer> seq : seqs) {
            for (int num : seq) nodes.add(num);
        }
        if (nodes.size() != org.length) return false;
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (int node : nodes) {
            graph.put(node, new HashSet<>());
            inDegree.put(node, 0);
        }
        for (List<Integer> seq : seqs) {
            for (int i = 0; i < seq.size() - 1; i++) {
                int from = seq.get(i), to = seq.get(i + 1);
                if (!graph.get(from).contains(to)) {
                    graph.get(from).add(to);
                    inDegree.put(to, inDegree.get(to) + 1);
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int node : org) {
            if (inDegree.get(node) == 0) queue.offer(node);
        }
        int idx = 0;
        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;
            int current = queue.poll();
            if (org[idx++] != current) return false;
            for (int nei : graph.get(current)) {
                inDegree.put(nei, inDegree.get(nei) - 1);
                if (inDegree.get(nei) == 0) queue.offer(nei);
            }
        }
        return idx == org.length;
    }

    // Driver code
    public static void main(String[] args) {
        int[] org = {1,2,3};
        List<List<Integer>> seqs = Arrays.asList(Arrays.asList(1,2), Arrays.asList(2,3));
        System.out.println(sequenceReconstruction(org, seqs)); // Expected: true
    }
}

Line Notes

Set<Integer> nodes = new HashSet<>();Collect all unique nodes from seqs to validate input

if (nodes.size() != org.length) return false;If nodes differ from org, reconstruction impossible

if (queue.size() > 1) return false;More than one node with zero in-degree means multiple valid orders

if (org[idx++] != current) return false;Check if current node matches org order at index

#include <bits/stdc++.h>
using namespace std;

bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    if (seqs.empty()) return false;
    unordered_set<int> nodes;
    for (auto& seq : seqs) {
        for (int num : seq) nodes.insert(num);
    }
    if (nodes.size() != org.size()) return false;
    unordered_map<int, unordered_set<int>> graph;
    unordered_map<int, int> in_degree;
    for (int node : nodes) {
        graph[node] = unordered_set<int>();
        in_degree[node] = 0;
    }
    for (auto& seq : seqs) {
        for (int i = 0; i + 1 < (int)seq.size(); i++) {
            int from = seq[i], to = seq[i+1];
            if (graph[from].count(to) == 0) {
                graph[from].insert(to);
                in_degree[to]++;
            }
        }
    }
    queue<int> q;
    for (int node : org) {
        if (in_degree[node] == 0) q.push(node);
    }
    int idx = 0;
    while (!q.empty()) {
        if (q.size() > 1) return false;
        int current = q.front(); q.pop();
        if (org[idx++] != current) return false;
        for (int nei : graph[current]) {
            in_degree[nei]--;
            if (in_degree[nei] == 0) q.push(nei);
        }
    }
    return idx == (int)org.size();
}

int main() {
    vector<int> org = {1,2,3};
    vector<vector<int>> seqs = {{1,2},{2,3}};
    cout << (sequenceReconstruction(org, seqs) ? "true" : "false") << endl; // Expected: true
    return 0;
}

Line Notes

unordered_set<int> nodes;Collect all unique nodes from seqs to validate input

if (nodes.size() != org.size()) return false;If nodes differ from org, reconstruction impossible

if (q.size() > 1) return false;More than one node with zero in-degree means multiple valid orders

if (org[idx++] != current) return false;Check if current node matches org order at index

function sequenceReconstruction(org, seqs) {
    if (!seqs || seqs.length === 0) return false;
    const nodes = new Set();
    for (const seq of seqs) {
        for (const num of seq) nodes.add(num);
    }
    if (nodes.size !== org.length) return false;
    const graph = new Map();
    const inDegree = new Map();
    for (const node of nodes) {
        graph.set(node, new Set());
        inDegree.set(node, 0);
    }
    for (const seq of seqs) {
        for (let i = 0; i < seq.length - 1; i++) {
            const from = seq[i], to = seq[i+1];
            if (!graph.get(from).has(to)) {
                graph.get(from).add(to);
                inDegree.set(to, inDegree.get(to) + 1);
            }
        }
    }
    const queue = [];
    for (const node of org) {
        if (inDegree.get(node) === 0) queue.push(node);
    }
    let idx = 0;
    while (queue.length > 0) {
        if (queue.length > 1) return false;
        const current = queue.shift();
        if (org[idx++] !== current) return false;
        for (const nei of graph.get(current)) {
            inDegree.set(nei, inDegree.get(nei) - 1);
            if (inDegree.get(nei) === 0) queue.push(nei);
        }
    }
    return idx === org.length;
}

// Driver code
const org = [1,2,3];
const seqs = [[1,2],[2,3]];
console.log(sequenceReconstruction(org, seqs)); // Expected: true

Line Notes

const nodes = new Set();Collect all unique nodes from seqs to validate input

if (nodes.size !== org.length) return false;If nodes differ from org, reconstruction impossible

if (queue.length > 1) return false;More than one node with zero in-degree means multiple valid orders

if (org[idx++] !== current) return false;Check if current node matches org order at index

⏱

Complexity

TimeO(n + m) where n is length of org and m is total length of seqs

SpaceO(n + m) for graph and in-degree storage

We build the graph and perform a BFS topological sort once, processing each edge and node once.

💡 For n=10^5 and m=10^5, this approach is efficient and scalable.

Interview Verdict: Accepted

This is the standard and efficient approach expected in interviews for this problem.

🧠

Graph Construction + DFS Postorder Topological Sort with Uniqueness Check

💡 This approach uses DFS to perform a postorder topological sort and checks if the order matches org uniquely by verifying edges and order consistency.

Intuition

DFS postorder gives a topological order. We verify if the order matches org and if the graph structure enforces uniqueness by checking adjacency constraints.

Algorithm

1. Build graph and track visited states for cycle detection.
2. Perform DFS postorder traversal to get topological order.
3. Reverse the postorder to get candidate order.
4. Check if candidate order matches org and if edges enforce uniqueness.
5. Return true if all checks pass, else false.

💡 DFS requires careful cycle detection and postorder reversal; uniqueness check is subtle and involves verifying adjacency matches.

</>

Code

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

def sequenceReconstruction(org, seqs):
    graph = defaultdict(set)
    nodes = set()
    for seq in seqs:
        for num in seq:
            nodes.add(num)
    if nodes != set(org):
        return False
    for seq in seqs:
        for i in range(len(seq) - 1):
            graph[seq[i]].add(seq[i+1])
    visited = {}
    stack = []
    def dfs(node):
        if node in visited:
            return visited[node]  # True if no cycle, False if cycle
        visited[node] = False  # mark as visiting
        for nei in graph[node]:
            if not dfs(nei):
                return False
        visited[node] = True  # mark as visited
        stack.append(node)
        return True
    for node in org:
        if node not in visited:
            if not dfs(node):
                return False
    stack.reverse()
    if stack != org:
        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

# Driver code
if __name__ == '__main__':
    org = [1,2,3]
    seqs = [[1,2],[2,3]]
    print(sequenceReconstruction(org, seqs))  # Expected: True

Line Notes

visited = {}Track node states: False=visiting, True=visited for cycle detection

visited[node] = FalseMark node as visiting to detect cycles

stack.append(node)Add node to postorder stack after visiting descendants

stack.reverse()Reverse postorder to get topological order

import java.util.*;

public class Solution {
    private static Map<Integer, Set<Integer>> graph = new HashMap<>();
    private static Map<Integer, Boolean> visited = new HashMap<>();
    private static List<Integer> stack = new ArrayList<>();

    public static boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Set<Integer> nodes = new HashSet<>();
        for (List<Integer> seq : seqs) {
            for (int num : seq) nodes.add(num);
        }
        if (nodes.size() != org.length) return false;
        for (int node : nodes) {
            graph.put(node, new HashSet<>());
        }
        for (List<Integer> seq : seqs) {
            for (int i = 0; i < seq.size() - 1; i++) {
                graph.get(seq.get(i)).add(seq.get(i + 1));
            }
        }
        for (int node : nodes) {
            visited.put(node, null);
        }
        for (int node : org) {
            if (visited.get(node) == null) {
                if (!dfs(node)) return false;
            }
        }
        Collections.reverse(stack);
        if (stack.size() != org.length) return false;
        for (int i = 0; i < org.length; i++) {
            if (stack.get(i) != org[i]) return false;
        }
        Map<Integer, Integer> pos = new HashMap<>();
        for (int i = 0; i < org.length; i++) pos.put(org[i], i);
        for (int u : graph.keySet()) {
            for (int v : graph.get(u)) {
                if (pos.get(u) >= pos.get(v)) return false;
            }
        }
        return true;
    }

    private static boolean dfs(int node) {
        visited.put(node, false);
        for (int nei : graph.get(node)) {
            Boolean state = visited.get(nei);
            if (state == null) {
                if (!dfs(nei)) return false;
            } else if (state == false) {
                return false;
            }
        }
        visited.put(node, true);
        stack.add(node);
        return true;
    }

    // Driver code
    public static void main(String[] args) {
        int[] org = {1,2,3};
        List<List<Integer>> seqs = Arrays.asList(Arrays.asList(1,2), Arrays.asList(2,3));
        System.out.println(sequenceReconstruction(org, seqs)); // Expected: true
    }
}

Line Notes

visited.put(node, false);Mark node as visiting to detect cycles

if (state == false) { return false; }Cycle detected if visiting node encountered again

stack.add(node);Add node to postorder stack after visiting descendants

Collections.reverse(stack);Reverse postorder to get topological order

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, unordered_set<int>> graph;
unordered_map<int, int> visited; // 0=unvisited,1=visiting,2=visited
vector<int> stack;

bool dfs(int node) {
    visited[node] = 1;
    for (int nei : graph[node]) {
        if (visited[nei] == 0) {
            if (!dfs(nei)) return false;
        } else if (visited[nei] == 1) {
            return false;
        }
    }
    visited[node] = 2;
    stack.push_back(node);
    return true;
}

bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
    unordered_set<int> nodes;
    for (auto& seq : seqs) {
        for (int num : seq) nodes.insert(num);
    }
    if (nodes.size() != org.size()) return false;
    for (int node : nodes) graph[node] = unordered_set<int>();
    for (auto& seq : seqs) {
        for (int i = 0; i + 1 < (int)seq.size(); i++) {
            graph[seq[i]].insert(seq[i+1]);
        }
    }
    for (int node : nodes) visited[node] = 0;
    for (int node : org) {
        if (visited[node] == 0) {
            if (!dfs(node)) return false;
        }
    }
    reverse(stack.begin(), stack.end());
    if ((int)stack.size() != (int)org.size()) return false;
    for (int i = 0; i < (int)org.size(); i++) {
        if (stack[i] != org[i]) return false;
    }
    unordered_map<int, int> pos;
    for (int i = 0; i < (int)org.size(); i++) pos[org[i]] = i;
    for (auto& [u, neighbors] : graph) {
        for (int v : neighbors) {
            if (pos[u] >= pos[v]) return false;
        }
    }
    return true;
}

int main() {
    vector<int> org = {1,2,3};
    vector<vector<int>> seqs = {{1,2},{2,3}};
    cout << (sequenceReconstruction(org, seqs) ? "true" : "false") << endl; // Expected: true
    return 0;
}

Line Notes

visited[node] = 1;Mark node as visiting to detect cycles

if (visited[nei] == 1) { return false; }Cycle detected if visiting node encountered again

stack.push_back(node);Add node to postorder stack after visiting descendants

reverse(stack.begin(), stack.end());Reverse postorder to get topological order

function sequenceReconstruction(org, seqs) {
    const graph = new Map();
    const nodes = new Set();
    for (const seq of seqs) {
        for (const num of seq) nodes.add(num);
    }
    if (nodes.size !== org.length) return false;
    for (const node of nodes) graph.set(node, new Set());
    for (const seq of seqs) {
        for (let i = 0; i < seq.length - 1; i++) {
            graph.get(seq[i]).add(seq[i+1]);
        }
    }
    const visited = new Map(); // null=unvisited, false=visiting, true=visited
    const stack = [];
    function dfs(node) {
        if (visited.has(node)) {
            if (visited.get(node) === false) return false;
            return true;
        }
        visited.set(node, false);
        for (const nei of graph.get(node)) {
            if (!dfs(nei)) return false;
        }
        visited.set(node, true);
        stack.push(node);
        return true;
    }
    for (const node of org) {
        if (!visited.has(node)) {
            if (!dfs(node)) return false;
        }
    }
    stack.reverse();
    if (stack.length !== org.length) return false;
    for (let i = 0; i < org.length; i++) {
        if (stack[i] !== org[i]) return false;
    }
    const pos = new Map();
    for (let i = 0; i < org.length; i++) pos.set(org[i], i);
    for (const [u, neighbors] of graph.entries()) {
        for (const v of neighbors) {
            if (pos.get(u) >= pos.get(v)) return false;
        }
    }
    return true;
}

// Driver code
const org = [1,2,3];
const seqs = [[1,2],[2,3]];
console.log(sequenceReconstruction(org, seqs)); // Expected: true

Line Notes

visited.set(node, false);Mark node as visiting to detect cycles

if (visited.get(node) === false) return false;Cycle detected if visiting node encountered again

stack.push(node);Add node to postorder stack after visiting descendants

stack.reverse();Reverse postorder to get topological order

⏱

Complexity

TimeO(n + m) where n is length of org and m is total length of seqs

SpaceO(n + m) for graph, visited map, and recursion stack

DFS visits each node and edge once; cycle detection and order verification add constant overhead.

💡 DFS is as efficient as BFS here but requires careful implementation to avoid cycles.

Interview Verdict: Accepted

This approach demonstrates mastery of DFS topological sort and uniqueness checks, useful for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 The BFS topological sort approach is the best balance of clarity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * m * k)	O(n)	Yes (deep recursion in permutations)	Yes, but impractical	Mention only - never code
2. BFS Topological Sort with Uniqueness Check	O(n + m)	O(n + m)	No	Yes, efficiently	Code this approach
3. DFS Postorder Topological Sort with Uniqueness Check	O(n + m)	O(n + m)	Possible (deep recursion)	Yes, with cycle detection	Discuss or code if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the BFS approach, and be ready to discuss DFS and brute force for completeness.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce graph construction and BFS topological sort with uniqueness check.Step 4: Code the BFS approach carefully.Step 5: Discuss DFS approach and edge cases if time permits.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of topological sort, cycle detection, uniqueness of order, and ability to implement graph algorithms efficiently.

Common Follow-ups

• What if seqs is empty or missing elements? → Return false since reconstruction impossible.
• How to detect cycles in the graph? → Use visited states in DFS or check if topological sort covers all nodes.

💡 These follow-ups test your robustness and understanding of graph properties beyond basic implementation.

🔍

Pattern Recognition

When to Use

1) Given partial sequences or constraints, 2) Need to reconstruct original order, 3) Check uniqueness of order, 4) Input can be modeled as graph edges

Signature Phrases

'sequence can be reconstructed uniquely''shortest common supersequence''given sequences are subsequences of original'

NOT This Pattern When

Problems that only ask for any topological order without uniqueness or reconstruction constraints

Similar Problems

Course Schedule II - find any valid topological orderAlien Dictionary - deduce character order from sequencesMinimum Height Trees - related graph ordering problem

Practice

1. Consider the following iterative DFS code to find all paths from source (0) to target in a DAG:

from typing import List

def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    target = len(graph) - 1
    res = []
    stack = [(0, [0])]

    while stack:
        node, path = stack.pop()
        if node == target:
            res.append(path)
        else:
            for nei in graph[node]:
                stack.append((nei, path + [nei]))
    return res

# Input graph: [[1,2],[3],[3],[]]
print(allPathsSourceTarget([[1,2],[3],[3],[]]))

What is the exact output of this code?

easy

A. [[0,1,3],[0,2,3]]

B. [[0,1,3]]

C. [[0,2,3],[0,1,3]]

D. [[0,1,2,3]]

Solution

1. Step 1: Trace stack operations

   Initial stack: [(0,[0])]. Pop (0,[0]), neighbors 1 and 2 pushed: stack=[(1,[0,1]),(2,[0,2])]. Next pop (2,[0,2]), neighbor 3 pushed: stack=[(1,[0,1]),(3,[0,2,3])]. Pop (3,[0,2,3]) -> target reached, add path.

2. Step 2: Continue tracing remaining stack

   Pop (1,[0,1]), neighbor 3 pushed: stack=[(3,[0,1,3])]. Pop (3,[0,1,3]) -> target reached, add path. Result order: [[0,2,3],[0,1,3]].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Stack is LIFO, so last neighbor pushed is processed first [OK]

Hint: Stack pops last pushed neighbor first, reversing neighbor order [OK]

Common Mistakes:

• Assuming neighbors processed in original order
• Confusing BFS order with DFS stack order

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

3. Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?

medium

A. Line 6: graph[a].append(b) -- edge direction reversed

B. Line 7: in_degree[a] += 1 -- incorrect in-degree increment

C. Line 10: queue initialization -- wrong nodes enqueued

D. Line 15: in_degree[nei] -= 1 -- decrementing in-degree incorrectly

Solution

1. Step 1: Analyze edge construction

   Prerequisite pairs are (a, b) meaning b -> a edge; reversing to graph[a].append(b) flips direction.

2. Step 2: Consequences of reversed edges

   In-degree counts and BFS queue become invalid, causing wrong order or infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct edge direction is critical for topological sort correctness [OK]

Hint: Check edge direction carefully when building graph [OK]

Common Mistakes:

• Reversing edges when building adjacency list
• Incrementing in-degree on wrong node
• Forgetting to decrement in-degree

4. What is the time complexity of the optimal topological sort + iterative DP solution for the longest path with different adjacent characters problem, given n nodes and m edges?

medium

A. O(n + m), since topological sort and DP each process nodes and edges once

B. O(n * m), because for each node we process all edges multiple times

C. O(n^2), because we must compare characters for every pair of nodes

D. O(m log n), due to sorting edges by character

Solution

1. Step 1: Identify topological sort complexity

   Topological sort runs in O(n + m) by processing each node and edge once.

2. Step 2: Analyze DP updates

   DP iterates over topo order and edges once, updating dp values in O(m) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both steps combined run in O(n + m) [OK]

Hint: Topological sort + DP each O(n + m), total O(n + m) [OK]

Common Mistakes:

• Confusing with O(n * m) due to nested loops
• Assuming character comparisons add extra complexity
• Thinking sorting edges is required

5. What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium

A. O(n²) because each leaf removal requires scanning all nodes.

B. O(n) because each edge and node is processed at most once during trimming.

C. O(n log n) due to priority queue operations for leaf selection.

D. O(n + m) where m is the number of edges, which equals n-1 here.

Solution

1. Step 1: Analyze leaf trimming operations

   Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.

2. Step 2: Combine node and edge processing

   Since the graph is a tree, edges = n-1. Total operations proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity matches leaf trimming algorithm [OK]

Hint: Each node and edge processed once [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing with BFS from each node
• Thinking priority queue is used