Topological Sort

1. 1.Course Schedule
   Kahn's Algorithm / Directed Cycle DFS: check if all courses can be finished (processedCount == n)medium
2. 2.Course Schedule II
   Return valid topological ordering array using Kahn's Queue or DFS Postorder Reversemedium
3. 3.Alien Dictionary
   Build character dependency edges from adjacent word differences + Topological Sort (check prefix rule)hard
4. 4.Find Eventual Safe States
   Reverse graph edges + Kahn's BFS starting from 0 out-degree nodesmedium
5. 5.Minimum Height Trees — related ordering idea
   Kahn's leaf-trimming BFS removing indegree 1 leaves until 1 or 2 tree centers remainmedium
6. 6.Parallel Courses
   Kahn's BFS level rings counting total semesters required to finish all coursesmedium
7. 7.Parallel Courses III
   Topological Sort + DP on DAG: dist[v] = max(dist[v], dist[u] + time[v])hard
8. 8.Find All Possible Recipes from Given Supplies
   Recipe ingredient dependency graph + Kahn's Algorithm initialized with suppliesmedium
9. 9.Build Order / Dependency Order
   Standard DAG Topological Sort on package build dependenciesmedium
10. 10.Sequence Reconstruction
    Verify unique topological ordering (Kahn's queue must never contain >1 node at any step)medium
11. 11.Sort Items by Groups Respecting Dependencies
    Double Topological Sort: 1st on groups, 2nd on items inside groupshard
12. 12.Largest Color Value in a Directed Graph
    Kahn's Topo Sort + DP state array dp[u][color] tracking max frequency of each colorhard
13. 13.Minimum Time to Complete All Tasks
    Interval scheduling / Topo order task duration optimizationmedium
14. 14.Find Eventual Safe States
    3-State Directed Cycle DFS / Reverse Kahn's Topological Sortmedium
15. 15.Directed Graph Cycle Detection
    Verify graph is a DAG prior to topological orderingmedium

1. 16.Topological Sort Using Kahn's Algorithm
   Indegree array + Queue initialized with indegree 0 nodesmedium
2. 17.Topological Sort Using DFS
   Recursive DFS postorder append + Reverse final array at the endmedium
3. 18.Detect Cycle in Directed Graph
   Topological Sort failure validation (len(order) < n)medium
4. 19.Build Systems Dependency Ordering
   Build DAG topological compilation sequencemedium
5. 20.Package Installation Order
   Package manager dependency resolution via Topo Sortmedium
6. 21.Task Scheduling With Prerequisites
   Multi-threaded worker pool execution of ready tasks (indegree 0)medium
7. 22.Strongly Connected Components — advanced relation
   Condensation DAG of strongly connected components sorted topologicallyhard
8. 23.Critical Path in DAG
   Topological Sort + DP finding longest duration path in project networkshard
9. 24.Shortest Path in DAG
   Topological Sort edge relaxation in O(V + E) timemedium

How to Think

1. Prerequisites / dependencies?Directed Graph + Topological Sort
2. Need valid execution order?Topological Sort
3. Need detect dependency cycle?Topological Sort fails (processedCount < n)
4. Process nodes as prerequisites complete?Kahn's Algorithm (Indegree 0 Queue)

// 1. Kahn's Algorithm (BFS Indegree 0 Queue): O(V + E) Time
func topoSortKahn(n int, edges [][]int) []int {
    adj := make([][]int, n)
    indegree := make([]int, n)

    for _, e := range edges {
        u, v := e[0], e[1] // Edge u -> v means u before v
        adj[u] = append(adj[u], v)
        indegree[v]++
    }

    queue := []int{}
    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i) // Ready nodes!
        }
    }

    order := []int{}
    head := 0

    for head < len(queue) {
        u := queue[head]
        head++
        order = append(order, u)

        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v) // Prerequisite satisfied!
            }
        }
    }

    if len(order) != n {
        return nil // Cycle detected! Not all nodes processed.
    }
    return order
}

// 2. DFS Topological Sort (Postorder Reverse): O(V + E) Time
func topoSortDFS(n int, adj [][]int) []int {
    state := make([]int, n) // 0=unvisited, 1=visiting, 2=finished
    order := []int{}

    var dfs func(u int) bool
    dfs = func(u int) bool {
        if state[u] == 1 { return false } // Cycle!
        if state[u] == 2 { return true }

        state[u] = 1
        for _, v := range adj[u] {
            if !dfs(v) { return false }
        }
        state[u] = 2
        order = append(order, u) // Postorder append!
        return true
    }

    for i := 0; i < n; i++ {
        if state[i] == 0 && !dfs(i) {
            return nil
        }
    }

    // Reverse order array to get valid Topological Order
    for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
        order[i], order[j] = order[j], order[i]
    }
    return order
}

Kahn's Algorithm (Indegree 0 Queue)

DFS Postorder Reverse & Parallel Waves

Topological Sort → Valid linear ordering for DAGs where u -> v implies u before v
Kahn's Algo      → Indegree 0 Queue -> Decrement neighbors -> Enqueue new 0s
Kahn Cycle Check → len(order) < n implies dependency deadlock cycle!
DFS Method       → Postorder append -> REVERSE final array
Alien Dict       → Compare adjacent words -> Build char topo graph

Common Interview Mistakes

Interview Rules

1. 1. Prerequisites / Dependencies? → Directed Graph Topological Sort
2. 2. Kahn's Algorithm? → Queue initialized with indegree == 0 nodes
3. 3. Processing step? → Pop node, append to order, decrement neighbor indegrees, enqueue new 0s
4. 4. Cycle validation? → If len(order) < n $\implies$ Cycle exists (return empty/nil)
5. 5. Course Schedule II? → Return valid topological order array
6. 6. Alien Dictionary? → Build char dependency graph from adjacent word diffs + Topo Sort
7. 7. Parallel execution waves? → Kahn BFS queue size level rings
8. 8. Overall Complexity → Time: O(V + E) | Space: O(V + E)

Topological Sort → Dependency Order for DAGs
u -> v           → u before v
Kahn's Algo      → Indegree 0 Queue
Indegree 0       → Ready to execute
Process          → Decrease neighbors' indegree
New 0            → Enqueue
Processed < N    → Cycle Deadlock!
DFS Method       → Postorder append -> REVERSE
Time             → O(V + E)

💡 Golden Rule: "A node becomes ready only when all of its prerequisites are finished; repeatedly process ready nodes until everything is ordered."