Topological Sort Pattern

1. Course Schedule Problem (Kahn's Algorithm)

Approach	Algorithm	Time	Space
DFS with Cycle Detection	White-Gray-Black coloring to detect cycles	`O(V + E)`	`O(V)`
Kahn's Algorithm (BFS)	Remove nodes with in-degree 0 iteratively	`O(V + E)`	`O(V)`
DFS Postorder	Add to result after exploring all children	`O(V + E)`	`O(V)`
Cycle Check Only	Return true/false without generating order	`O(V + E)`	`O(V)`

Example: DFS cycle detection

function canFinish(numCourses, prerequisites) {
    // Build adjacency list
    const graph = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
    }
    
    // 0: unvisited (white)
    // 1: visiting (gray - in current path)
    // 2: visited (black - fully processed)
    const state = new Array(numCourses).fill(0);
    
    function hasCycle(node) {
        if (state[node] === 1) return true;  // Cycle!
        if (state[node] === 2) return false; // Already checked
        
        state[node] = 1; // Mark as visiting
        
        for (const neighbor of graph[node]) {
            if (hasCycle(neighbor)) {
                return true;
            }
        }
        
        state[node] = 2; // Mark as visited
        return false;
    }
    
    // Check each node
    for (let i = 0; i < numCourses; i++) {
        if (state[i] === 0 && hasCycle(i)) {
            return false;
        }
    }
    
    return true;
}

// Example: numCourses=2, prerequisites=[[1,0]]
// Course 1 requires course 0
// Result: true (can finish: 0 -> 1)

Example: Kahn's algorithm (BFS)

function canFinishKahn(numCourses, prerequisites) {
    // Build graph and in-degree array
    const graph = Array.from({ length: numCourses }, () => []);
    const inDegree = new Array(numCourses).fill(0);
    
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
        inDegree[course]++;
    }
    
    // Queue of nodes with no prerequisites
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    let completed = 0;
    
    while (queue.length > 0) {
        const course = queue.shift();
        completed++;
        
        // Remove this course's edges
        for (const next of graph[course]) {
            inDegree[next]--;
            if (inDegree[next] === 0) {
                queue.push(next);
            }
        }
    }
    
    return completed === numCourses;
}

// If cycle exists, some nodes never reach in-degree 0
// completed < numCourses indicates cycle

Example: Course Schedule II - return topological order

function findOrder(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const inDegree = new Array(numCourses).fill(0);
    
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
        inDegree[course]++;
    }
    
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    
    const order = [];
    
    while (queue.length > 0) {
        const course = queue.shift();
        order.push(course);
        
        for (const next of graph[course]) {
            inDegree[next]--;
            if (inDegree[next] === 0) {
                queue.push(next);
            }
        }
    }
    
    // If cycle exists, order.length < numCourses
    return order.length === numCourses ? order : [];
}

// Example: numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
// Result: [0,1,2,3] or [0,2,1,3] (both valid)

2. Alien Dictionary Problem (Character Order)

Step	Action	Implementation	Edge Case
1. Build Graph	Compare adjacent words character by character	Find first differing char, add edge u→v	One word prefix of another (invalid if shorter first)
2. Track In-degrees	Count incoming edges for each character	Use Map for characters that appear	Characters with no edges still need 0 in-degree
3. Topological Sort	Kahn's algorithm on character graph	Process chars with in-degree 0	Cycle detection (invalid alien language)
4. Validate Result	Check if all characters processed	`order.length === graph.size`	Empty order indicates cycle or error

Example: Alien dictionary character order

function alienOrder(words) {
    // Build graph and in-degree map
    const graph = new Map();
    const inDegree = new Map();
    
    // Initialize: all characters have in-degree 0
    for (const word of words) {
        for (const char of word) {
            if (!graph.has(char)) {
                graph.set(char, new Set());
                inDegree.set(char, 0);
            }
        }
    }
    
    // Build edges by comparing adjacent words
    for (let i = 0; i < words.length - 1; i++) {
        const word1 = words[i];
        const word2 = words[i + 1];
        const minLen = Math.min(word1.length, word2.length);
        
        // Edge case: word1 is prefix of word2 but longer
        if (word1.length > word2.length && 
            word1.startsWith(word2)) {
            return ""; // Invalid
        }
        
        // Find first different character
        for (let j = 0; j < minLen; j++) {
            if (word1[j] !== word2[j]) {
                const u = word1[j];
                const v = word2[j];
                
                // Add edge u -> v if not exists
                if (!graph.get(u).has(v)) {
                    graph.get(u).add(v);
                    inDegree.set(v, inDegree.get(v) + 1);
                }
                break; // Only first difference matters
            }
        }
    }
    
    // Topological sort using Kahn's algorithm
    const queue = [];
    for (const [char, degree] of inDegree) {
        if (degree === 0) queue.push(char);
    }
    
    let order = '';
    
    while (queue.length > 0) {
        const char = queue.shift();
        order += char;
        
        for (const next of graph.get(char)) {
            inDegree.set(next, inDegree.get(next) - 1);
            if (inDegree.get(next) === 0) {
                queue.push(next);
            }
        }
    }
    
    // Check if valid (no cycle)
    return order.length === graph.size ? order : "";
}

// Example: ["wrt","wrf","er","ett","rftt"]
// Comparisons:
// "wrt" vs "wrf": t -> f
// "wrf" vs "er": w -> e
// "er" vs "ett": r -> t
// "ett" vs "rftt": e -> r
// Result: "wertf"

Note: Alien Dictionary is tricky because you must only compare first differing character between adjacent words. If "abc" comes before "ab", the dictionary is invalid (longer word cannot come first if it's a prefix). Always validate this edge case.

3. Build Order with Dependencies

Variation	Difference	Implementation	Use Case
Single Valid Order	Any topological order works	Standard Kahn's or DFS	Course schedule, build systems
All Valid Orders	Generate all possible orderings	Backtracking + in-degree tracking	Testing, dependency analysis
Lexicographically Smallest	Among valid orders, choose smallest	Use min-heap instead of queue	Deterministic build order
Parallel Execution	Group independent tasks by level	BFS level-by-level grouping	Task scheduling, parallel builds

Example: Lexicographically smallest topological order

function smallestOrder(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }
    
    // Use min-heap instead of regular queue
    const minHeap = new MinPriorityQueue({ priority: x => x });
    
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) {
            minHeap.enqueue(i);
        }
    }
    
    const order = [];
    
    while (!minHeap.isEmpty()) {
        const node = minHeap.dequeue().element;
        order.push(node);
        
        for (const next of graph[node]) {
            inDegree[next]--;
            if (inDegree[next] === 0) {
                minHeap.enqueue(next);
            }
        }
    }
    
    return order.length === n ? order : [];
}

// Using min-heap ensures we always pick smallest available node
// Result is lexicographically smallest valid topological order

Example: Group by parallel execution levels

function parallelBuildOrder(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }
    
    let queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    
    const levels = [];
    
    while (queue.length > 0) {
        const currentLevel = [...queue];
        levels.push(currentLevel);
        
        const nextQueue = [];
        
        for (const node of queue) {
            for (const next of graph[node]) {
                inDegree[next]--;
                if (inDegree[next] === 0) {
                    nextQueue.push(next);
                }
            }
        }
        
        queue = nextQueue;
    }
    
    return levels;
}

// Example: edges = [[0,2],[0,3],[1,3],[1,4]]
// Result: [[0,1], [2,3,4]]
// Level 0: tasks 0,1 can run in parallel
// Level 1: tasks 2,3,4 can run in parallel after level 0

4. All Topological Orderings of DAG

Approach	Method	Time	Space
Backtracking	Try each node with in-degree 0, recurse	`O(V! * E)`	`O(V)`
State Tracking	Maintain in-degree, used set, current path	Exponential	`O(V)` depth
Pruning	Only try nodes with current in-degree 0	Reduces branches	Critical optimization
Count Only	Count orderings instead of generating	Same complexity	More efficient

Example: Generate all topological orderings

function allTopologicalOrders(graph) {
    const n = graph.length;
    const inDegree = new Array(n).fill(0);
    
    // Calculate in-degrees
    for (let u = 0; u < n; u++) {
        for (const v of graph[u]) {
            inDegree[v]++;
        }
    }
    
    const result = [];
    const current = [];
    const visited = new Array(n).fill(false);
    
    function backtrack() {
        // Base case: all nodes processed
        if (current.length === n) {
            result.push([...current]);
            return;
        }
        
        // Try each node with current in-degree 0
        for (let i = 0; i < n; i++) {
            if (!visited[i] && inDegree[i] === 0) {
                // Choose this node
                visited[i] = true;
                current.push(i);
                
                // Reduce in-degree of neighbors
                for (const neighbor of graph[i]) {
                    inDegree[neighbor]--;
                }
                
                // Recurse
                backtrack();
                
                // Backtrack: restore state
                for (const neighbor of graph[i]) {
                    inDegree[neighbor]++;
                }
                current.pop();
                visited[i] = false;
            }
        }
    }
    
    backtrack();
    return result;
}

// Example: graph = [[1], [2], []]
// Nodes: 0 -> 1 -> 2
// Result: [[0,1,2]] (only one valid order)

// Example: graph = [[2], [2], []]
// Nodes: 0 -> 2, 1 -> 2
// Result: [[0,1,2], [1,0,2]] (two valid orders)

Warning: Generating all topological orderings has factorial time complexity in worst case (when graph is completely disconnected). Use only for small graphs (n ≤ 10). For larger graphs, generate one order or count orderings using DP.

5. Sequence Reconstruction Verification

Challenge	Condition	Check	Complexity
Uniqueness	Only one valid topological order	At most one node with in-degree 0 at each step	`O(V + E)`
Completeness	All consecutive pairs covered	Every edge in order exists in sequences	Check all pairs
Cycle Check	No cycles in dependency graph	Topological sort completes	Standard check
Coverage	All nodes appear in sequences	Union of sequences == all nodes	`O(total elements)`

Example: Verify sequence reconstruction

function sequenceReconstruction(nums, sequences) {
    const n = nums.length;
    const graph = new Map();
    const inDegree = new Map();
    
    // Initialize graph for all numbers
    for (const num of nums) {
        graph.set(num, new Set());
        inDegree.set(num, 0);
    }
    
    // Build graph from sequences
    for (const seq of sequences) {
        for (let i = 0; i < seq.length - 1; i++) {
            const u = seq[i];
            const v = seq[i + 1];
            
            // Validate numbers are in range
            if (!graph.has(u) || !graph.has(v)) {
                return false;
            }
            
            // Add edge if not exists
            if (!graph.get(u).has(v)) {
                graph.get(u).add(v);
                inDegree.set(v, inDegree.get(v) + 1);
            }
        }
    }
    
    // Topological sort with uniqueness check
    const queue = [];
    for (const [num, degree] of inDegree) {
        if (degree === 0) queue.push(num);
    }
    
    const order = [];
    
    while (queue.length > 0) {
        // CRITICAL: Must have exactly one node with in-degree 0
        if (queue.length > 1) {
            return false; // Not unique
        }
        
        const num = queue.shift();
        order.push(num);
        
        for (const next of graph.get(num)) {
            inDegree.set(next, inDegree.get(next) - 1);
            if (inDegree.get(next) === 0) {
                queue.push(next);
            }
        }
    }
    
    // Check if we got complete order matching nums
    if (order.length !== n) return false;
    
    for (let i = 0; i < n; i++) {
        if (order[i] !== nums[i]) return false;
    }
    
    return true;
}

// Example: nums = [1,2,3], sequences = [[1,2],[1,3]]
// Result: false (both [1,2,3] and [1,3,2] are valid)

// Example: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
// Result: true (only [1,2,3] is valid)

// Key: queue.length > 1 means multiple valid orderings exist

Example: Alternative - check pairs coverage

function sequenceReconstructionAlt(nums, sequences) {
    const n = nums.length;
    const pairs = new Set();
    
    // Collect all consecutive pairs from sequences
    for (const seq of sequences) {
        for (let i = 0; i < seq.length - 1; i++) {
            pairs.add(`${seq[i]},${seq[i+1]}`);
        }
    }
    
    // Check if all consecutive pairs in nums are covered
    for (let i = 0; i < n - 1; i++) {
        if (!pairs.has(`${nums[i]},${nums[i+1]}`)) {
            return false; // Missing edge
        }
    }
    
    // Build graph and check uniqueness via topological sort
    const graph = new Map();
    const inDegree = new Map();
    
    for (const num of nums) {
        graph.set(num, new Set());
        inDegree.set(num, 0);
    }
    
    for (const seq of sequences) {
        for (let i = 0; i < seq.length - 1; i++) {
            const u = seq[i];
            const v = seq[i + 1];
            
            if (!graph.has(u) || !graph.has(v)) return false;
            
            if (!graph.get(u).has(v)) {
                graph.get(u).add(v);
                inDegree.set(v, inDegree.get(v) + 1);
            }
        }
    }
    
    // Verify uniqueness (same as before)
    let queue = [];
    for (const [num, degree] of inDegree) {
        if (degree === 0) queue.push(num);
    }
    
    while (queue.length > 0) {
        if (queue.length > 1) return false;
        
        const num = queue.shift();
        for (const next of graph.get(num)) {
            inDegree.set(next, inDegree.get(next) - 1);
            if (inDegree.get(next) === 0) queue.push(next);
        }
    }
    
    return true;
}

// Two conditions must hold:
// 1. All pairs in nums exist in sequences (coverage)
// 2. Only one topological order exists (uniqueness)

Summary: Topological Sort Patterns

Two Main Algorithms: DFS postorder (add to result after exploring children) and Kahn's BFS (process nodes with in-degree 0)
DFS Cycle Detection: Three states: unvisited (white), visiting (gray - in current path), visited (black) - cycle if revisit gray node
Kahn's Algorithm: Initialize queue with in-degree 0 nodes, process each, decrement neighbors' in-degree, add to queue when 0
Cycle Detection Kahn's: If processed nodes < total nodes, cycle exists (some nodes never reach in-degree 0)
Course Schedule: Can finish if no cycles - use either DFS cycle detection or Kahn's with count check
Alien Dictionary: Compare adjacent words for first difference, add edge for character ordering, validate prefix edge case
Prefix Edge Case: If word1.startsWith(word2) but word1.length > word2.length, dictionary is invalid
Lexicographically Smallest: Use min-heap instead of queue in Kahn's algorithm to always pick smallest available node
Parallel Execution: Group by BFS levels - all nodes in same level can execute in parallel
All Orderings: Backtracking with in-degree tracking - try each in-degree 0 node, recurse, restore state - O(V!) complexity
Sequence Reconstruction: Verify uniqueness (queue.length ≤ 1 at each step) and completeness (all pairs in target exist in sequences)
Uniqueness Check: During Kahn's, if queue.length > 1, multiple valid orderings exist - order is not unique
Applications: Build systems, dependency resolution, task scheduling, compiler optimization, package managers

Related Cheat Sheets

Datastructures Algorithms