> For the complete documentation index, see [llms.txt](https://chkrishnatej.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chkrishnatej.gitbook.io/interview-prep/graphs/khans-algorithm.md).

# Khans Algorithm

### Kahn's Algorithm - Building Graph

Before building any graph, ask yourself:

> **"What does it mean for a node to be READY to process?"**

* Ready = has no unsatisfied prerequisites → track **indegree** → standard Kahn's
* Ready = has no unresolved outgoing paths → track **outdegree** → **reverse the graph**, then track indegree

The algorithm never changes. Only the graph direction changes to match the semantics.

***

### One Core Question Kahn's Answers

> **"What gets unlocked when I finish this node?"**

That's it. Every design decision about graph construction flows from this.

When Kahn's pulls a node from the queue, it needs to look at its neighbours and say *"I can now reduce your dependency count."* This means **edges must point forward** — from dependency to dependent.

{% tabs %}
{% tab title="Main Intution" %}
Once you have this skeleton cold, every Kahn's problem becomes just two decisions:

* How do I construct the edge `u → v` for this specific problem?
* Do I need to record the order, or just detect a cycle?
  {% endtab %}
  {% endtabs %}

***

### The 5 Problem Archetypes

#### 1. Cycle Detection in Directed Graph

> *"Is this system of dependencies valid / conflict-free?"*

Kahn's naturally detects cycles — if not all nodes are processed, a cycle exists. Nodes stuck with indegree > 0 are part of the cycle.

<table><thead><tr><th width="233.03515625">Example</th><th>Cycle means</th></tr></thead><tbody><tr><td>Course prerequisites</td><td>Impossible to graduate</td></tr><tr><td>Package dependencies</td><td>Circular import</td></tr><tr><td>Task scheduling</td><td>Deadlock</td></tr></tbody></table>

***

#### 2. Topological Ordering

> *"In what order should I process these dependent tasks?"*

The BFS order Kahn's produces is a valid topological sort. Multiple valid orderings may exist — Kahn's gives you one of them.

| Example                      | Order means                 |
| ---------------------------- | --------------------------- |
| Course Schedule II           | Order to take courses       |
| Build systems (Maven/Gradle) | Order to compile modules    |
| Database migrations          | Order to run schema changes |

***

#### 3. Finding Safe / Reachable Nodes

> *"Which nodes are guaranteed to not be part of a cycle?"*

Reverse the graph, run Kahn's. Every node that gets processed is a safe node. Nodes never processed are stuck in a cycle.

| Example              | Safe means                            |
| -------------------- | ------------------------------------- |
| Eventual Safe States | Node whose all paths lead to terminal |
| Virus spread         | Nodes that can't be infected          |

***

#### 4. Level-by-Level Processing (BFS layering)

> *"What can be done in parallel at each step?"*

Kahn's processes nodes in waves — all indegree-0 nodes in one wave, then the next batch, etc. This maps directly to parallel execution stages.

| Example                  | Level means                        |
| ------------------------ | ---------------------------------- |
| Parallel courses         | Minimum semesters to finish        |
| Project scheduling (CPM) | Minimum time with parallel workers |
| Compilation stages       | Which files compile in parallel    |

***

#### 5. Ordering With Constraints / Reconstruction

> *"Given partial ordering rules, reconstruct the full sequence."*

When you're given pairwise ordering constraints and must reconstruct the full sequence, Kahn's turns those constraints into edges and produces the order.

| Example                 | Constraint means                        |
| ----------------------- | --------------------------------------- |
| Alien Dictionary        | Character ordering rules from word list |
| Sequence Reconstruction | Verify if unique topo order exists      |
| Task with cooldown      | Process tasks respecting gaps           |

***

### The Canonical Signal

> Any time you see the words: **"dependency", "prerequisite", "before/after", "order", "safe", "deadlock", "parallel stages"** — think Kahn's first.

***

### Practice Problems - Grouped by Archetype

#### 🟢 Archetype 1 — Cycle Detection

<table><thead><tr><th width="57.953125">#</th><th>Problem</th><th>Difficulty</th><th>Key Insight</th></tr></thead><tbody><tr><td>1</td><td>Course Schedule I (LC 207)</td><td>Medium</td><td>Classic Kahn's — return boolean</td></tr><tr><td>2</td><td>Find if Path Exists in Graph (LC 1971)</td><td>Easy</td><td>Warm-up — understand graph basics</td></tr><tr><td>3</td><td>Detect Cycle in Directed Graph</td><td>Medium</td><td>Nodes with indegree > 0 after Kahn's = cycle</td></tr></tbody></table>

***

#### 🟡 Archetype 2 - Topological Order

<table><thead><tr><th width="58.22265625">#</th><th>Problem</th><th>Difficulty</th><th>Key Insight</th></tr></thead><tbody><tr><td>4</td><td>Course Schedule II (LC 210)</td><td>Medium</td><td>Classic Kahn's — return order array</td></tr><tr><td>5</td><td>Alien Dictionary (LC 269)</td><td>Hard</td><td>Build graph from character pairs, then topo sort</td></tr><tr><td>6</td><td>Sequence Reconstruction (LC 444)</td><td>Medium</td><td>Check if unique topo order exists</td></tr><tr><td>7</td><td>Sort Items by Groups (LC 1203)</td><td>Hard</td><td>Two-level topo sort — items within groups, then groups</td></tr></tbody></table>

***

#### 🟡 Archetype 3 - Safe / Reachable Nodes

<table><thead><tr><th width="54.39453125">#</th><th>Problem</th><th>Difficulty</th><th>Key Insight</th></tr></thead><tbody><tr><td>8</td><td>Eventual Safe States (LC 802)</td><td>Medium</td><td>Reverse graph + Kahn's</td></tr><tr><td>9</td><td>Minimum Height Trees (LC 310)</td><td>Medium</td><td>Reverse thinking — trim leaves inward</td></tr></tbody></table>

***

#### 🟠 Archetype 4 - Level-by-Level / Parallel Processing

<table><thead><tr><th width="57.24609375">#</th><th>Problem</th><th>Difficulty</th><th>Key Insight</th></tr></thead><tbody><tr><td>10</td><td>Parallel Courses (LC 1136)</td><td>Medium</td><td>Count BFS levels = minimum semesters</td></tr><tr><td>11</td><td>Parallel Courses III (LC 2050)</td><td>Hard</td><td>Track earliest finish time per node</td></tr><tr><td>12</td><td>Jump Game IV (LC 1345)</td><td>Hard</td><td>BFS levels = minimum jumps</td></tr></tbody></table>

***

#### 🔴 Archetype 5 - Ordering With Constraints

<table><thead><tr><th width="68.5078125">#</th><th>Problem</th><th>Difficulty</th><th>Key Insight</th></tr></thead><tbody><tr><td>13</td><td>Task Scheduler (LC 621)</td><td>Medium</td><td>Greedy + frequency, Kahn's variant</td></tr><tr><td>14</td><td>Largest Number (LC 179)</td><td>Medium</td><td>Custom comparator — disguised ordering</td></tr><tr><td>15</td><td>Build a Matrix With Conditions (LC 2392)</td><td>Hard</td><td>Two independent topo sorts — row and column</td></tr></tbody></table>

***

### Code

#### Classic Khans Algorithm - Cycle Detection:

```java
/**
 * Classic Kahn's Algorithm
 * Goal: Detect if a cycle exists in a directed graph
 * 
 * Input:  n = number of nodes
 *         edges = list of directed edges [u, v] meaning u → v
 * Output: true if no cycle exists, false if cycle detected
 */
public boolean canFinish(int n, int[][] edges) {
    // Step 1: Build adjacency list
    // graph.get(u) = list of nodes that u unlocks
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    // Step 2: Build indegree array
    int[] indegree = new int[n];

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // u must come before v, so edge u → v
        graph.get(u).add(v);
        indegree[v]++;  // v has one more dependency
    }

    // Step 3: Seed the queue with all indegree-0 nodes
    // These are nodes with no dependencies — free to process immediately
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }

    // Step 4: BFS — process nodes and unlock their dependents
    int processed = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        processed++;

        for (int v : graph.get(u)) {
            // "u is done, so v has one fewer blocker"
            indegree[v]--;
            if (indegree[v] == 0) queue.offer(v);
        }
    }

    // Step 5: Cycle check
    // If processed < n, some nodes were never unblocked → cycle exists
    return processed == n;
}
```

#### Khans with path tracking

```java
/**
 * Kahn's Algorithm — Topological Order
 * Goal: Return a valid topological ordering of nodes
 *
 * Input:  n = number of nodes
 *         edges = list of directed edges [u, v] meaning u → v
 * Output: valid topological order, or empty array if cycle exists
 */
public int[] findOrder(int n, int[][] edges) {
    // Step 1: Build adjacency list
    // graph.get(u) = list of nodes that u unlocks
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    // Step 2: Build indegree array
    int[] indegree = new int[n];

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        // u must come before v, so edge u → v
        graph.get(u).add(v);
        indegree[v]++;  // v has one more dependency
    }

    // Step 3: Seed the queue with all indegree-0 nodes
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }

    // Step 4: BFS — record order as we process each node
    int[] order = new int[n];
    int idx = 0;

    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;  // ← only addition vs classic version

        for (int v : graph.get(u)) {
            // "u is done, so v has one fewer blocker"
            indegree[v]--;
            if (indegree[v] == 0) queue.offer(v);
        }
    }

    // Step 5: Cycle check — same as classic
    // Additionally return the order if no cycle
    return (idx == n) ? order : new int[]{};
}
```

***

### The Three-Step Mental Model

#### Step 1: Identify "what blocks what"

Before touching code, ask:

> *"Node A must come before Node B",* write this as a sentence for your specific problem.

| Problem              | Sentence                                            | Edge                     |
| -------------------- | --------------------------------------------------- | ------------------------ |
| Course Schedule      | Prereq must come before Course                      | `prereq → course`        |
| Task dependencies    | Task A must finish before Task B                    | `A → B`                  |
| Eventual Safe States | Terminal node "unlocks" its predecessors (reversed) | `v → u` (reversed graph) |
| Build order          | Library must be built before App                    | `library → app`          |

#### Step 2: Identify your "free" starting nodes

Ask:

> *"Which nodes have nothing blocking them?"*

That translates directly to **indegree = 0** in your constructed graph.

| Problem              | Starting node                | Why indegree = 0                                        |
| -------------------- | ---------------------------- | ------------------------------------------------------- |
| Course Schedule      | Course with no prerequisites | Nothing blocks it                                       |
| Eventual Safe States | Terminal node                | No outgoing edges in original = no incoming in reversed |
| Alien Dictionary     | First letter in ordering     | Nothing comes before it                                 |

#### Step 3: Verify the propagation makes sense

When you process node `u` and decrement neighbours' indegree, ask:

> *"Does it make sense that finishing `u` removes one dependency from `v`?"*

If yes → your graph is constructed correctly. If no → your edges are reversed, flip them.

**What Is Step 3 Actually Asking?**

When Kahn's processes node `u`, it does this:

```java
for (int v : graph.get(u)) {
    indegree[v]--;
    if (indegree[v] == 0) queue.offer(v);
}
```

Step 3 asks you to **read this in plain English** and check if it makes sense for your problem.

> *"I just finished `u`. So I am removing one dependency from `v`."*

* If that sentence sounds right → your graph is correct.
* If that sentence sounds wrong → your edges are flipped.

***

### The Two Situations You'll Always Encounter

```
SITUATION 1: Problem gives you "A must come before B"
─────────────────────────────────────────────────────
Edge: A → B
Indegree of B increases
Start from nodes with indegree = 0 (nothing before them)
↓
Direct Kahn's — no reversal needed

SITUATION 2: Problem gives you "A points to B" but you 
want to start from the OTHER end (like safe states)
─────────────────────────────────────────────────────
Edge in original: A → B  
But you want to start from B (terminal/sink nodes)
↓
Reverse the graph: B → A
Now B has indegree = 0 → Kahn's starts there
```

***

### The Indegree Invariant

This is the contract Kahn's relies on:

> **indegree\[v] = number of unprocessed nodes that must come before v**

When this count hits 0, `v` is ready. Your graph construction **must** preserve this invariant.

This is why the edge direction is non-negotiable — if you flip edges, indegree counts the wrong thing and the invariant breaks.

***

### Decision Checklist Before Coding

```
1. Write one sentence: "X must come before Y"
         ↓
2. Draw edge: X → Y
         ↓
3. Ask: "Which nodes have indegree 0?"
   Are those the natural starting points? 
         ↓ YES              ↓ NO
   Build graph directly   Reverse the graph
         ↓
4. When processing node u, ask:
   "Does decrementing graph[u]'s neighbours' 
    indegree make semantic sense?"
         ↓ YES              ↓ NO  
   You're done            Debug edge direction
```

***

### Why DFS Doesn't Need This

DFS-based topo sort doesn't care about edge direction the same way because:

* It uses **post-order + stack** (or reverse of finishing time)
* The stack reversal compensates for edge direction
* You can build edges as `course → prereq` and still get correct order

This is exactly why your earlier DFS solution worked with `graph.get(course).add(prereq)` — two inversions cancelled out.

**Kahn's has no such cancellation mechanism.** It's a forward-propagating algorithm, so the graph must be forward-oriented from the start.

***

### One-Line Summary

> **Build the graph so that `graph.get(u)` answers: "who gets unblocked when u is done?"**

If the problem gives you that directly → use it as-is. If the problem gives you the opposite → reverse it.