Loading…

mediumGraphsLC #207Asked very often

Course Schedule (Topological Sort)

Q: How do you solve Course Schedule (Topological Sort) using the Kahn's Algorithm — Indegree BFS (Topological Sort) approach?

When to use it: The go-to answer. Phrase it as 'repeatedly take any course with no remaining prerequisites'. It naturally produces an order too. Kahn's algorithm peels the graph from its 'roots' inward. **Indegree = number of unmet prerequisites.** A course with indegree 0 has nothing blocking it, so it can be taken immediately. We seed a queue with all such courses. **Taking a course unlocks its dependents.** When we 'take' (dequeue) a course `u`, every course `v` that listed `u` as a prerequisite loses one blocker — decrement `indegree[v]`. If that drops `v` to 0, all of `v`'s prerequisites are now satisfied, so we enqueue it. This ripples through the DAG layer by layer. **The cycle test is a simple count.** Track how many courses we successfully process. In an acyclic graph every node eventually reaches indegree 0 and gets processed, so `processed == numCourses`. If there's a cycle, the nodes inside it perpetually block each other — none ever reaches indegree 0 — so the queue empties early and `processed < numCourses`. That comparison is the entire answer. **Bonus: it gives an order.** The sequence in which we dequeue courses is a valid topological order. That's exactly what Course Schedule II asks for; here we only need the count, but it's worth mentioning to show depth. Time complexity: O(V + E). Space complexity: O(V + E).

Q: How do you solve Course Schedule (Topological Sort) using the DFS with Three-Color Cycle Detection approach?

When to use it: Offer as the recursive alternative. Stress the three states — a plain visited set can't detect directed cycles. Detect a cycle by watching for an edge back into the path we're currently on. **Why two states aren't enough.** In an undirected graph a visited set suffices, but directed graphs need to distinguish 'visited on *this* path' from 'visited and finished'. Consider a diamond `A→B, A→C, B→D, C→D`: D is reached twice but there's no cycle. A 2-state set would falsely flag the second visit. We need to know whether the node we re-reach is still *open* on the current recursion stack. **Three colors.** `0` = white (untouched), `1` = gray (in progress, on the current DFS path), `2` = black (finished, all descendants explored). When we start exploring a node we paint it gray; after recursing into all its children we paint it black. **The cycle rule.** During DFS from node `u`, if we follow an edge to a node that is **gray**, we've found a back edge to an ancestor still on our path — a cycle — so return false. If it's **black**, it's a finished subtree with no cycle (like D in the diamond) and we can safely skip it. **Driver loops over all nodes.** Because the graph may be disconnected, we launch DFS from every still-white node. If any DFS reports a cycle, the answer is false; otherwise all courses are completable. Time complexity: O(V + E). Space complexity: O(V + E).

LCPractice

Graphs · 2 of 34 · 11 min

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [aᵢ, bᵢ] indicates that you must take course `bᵢ` first if you want to take course aᵢ.

Return true if you can finish all courses. Otherwise, return false.

In plain English

Each course is a node; each prerequisite pair [a, b] is a directed edge b → a ('do b before a'). You can complete every course exactly when these dependencies contain no cyclic deadlock. So the question is purely: is the directed graph acyclic?

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Note: Edge 0 → 1: take 0 then 1. No cycle, so all courses are completable.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Note: Edges 0 → 1 and 1 → 0 form a cycle; neither course can start first.

Example 3

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Note: 0 → 1, 0 → 2, 1 → 3, 2 → 3 is a DAG; a valid order is 0,1,2,3.

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000
prerequisites[i].length == 2
0 ≤ aᵢ, bᵢ < numCourses
All the pairs prerequisites[i] are distinct

Clarifying questions4First question: Which way does the edge point — from prerequisite or to it?Explore questions

Q1.Which way does the edge point — from prerequisite or to it?
[a, b] means b is required before a, so I'll draw b → a. I confirm direction explicitly because reversing it silently breaks the indegree logic.
Q2.Can there be duplicate or self-loop prerequisites?
Pairs are distinct per constraints. A self-loop [a, a] would be an immediate cycle → false; I'd handle it naturally since it gives a node indegree it can never clear.
Q3.Do I need the actual order or just feasibility?
Just true/false here. If the order were required, that's Course Schedule II — I'd emit Kahn's pop sequence.
Q4.Could the graph be disconnected?
Yes — multiple independent course clusters. Kahn's handles that automatically by seeding all indegree-0 nodes; DFS must loop over every unvisited node.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Model prerequisites as a directed graph (b → a means 'take b before a'). You can finish all courses iff the graph has no cycle. Kahn's algorithm: repeatedly remove nodes with indegree 0; if you process all n nodes, no cycle exists. Equivalently, DFS with three-color marking detects a back edge (cycle). Both run in O(V + E).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you translate prerequisites into a directed graph with a consistent edge direction, and whether you know that 'can finish' reduces to 'is acyclic' — solved by topological sort.

Where candidates slip

Reversing the edge direction, using a 2-state visited set for directed cycle detection (misses back edges), or building the graph but never checking for the cycle.

How to stand out

State the reduction to cycle detection, present Kahn's (intuitive, also yields an order) AND DFS three-coloring, explain why gray/in-progress is needed, and mention Course Schedule II returns the actual order.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Kahn's Algorithm — Indegree BFS (Topological Sort)	`O(V + E)`	`O(V + E)`	The go-to answer. Phrase it as 'repeatedly take any course with no remaining prerequisites'. It naturally produces an order too.	Read
2	DFS with Three-Color Cycle DetectionOptimal	`O(V + E)`	`O(V + E)`	Offer as the recursive alternative. Stress the three states — a plain visited set can't detect directed cycles.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCan finish all courses?Want an explicit order too?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Kahn's Algorithm — Indegree BFS (Topological Sort)

TimeO(V + E)SpaceO(V + E)

The go-to answer. Phrase it as 'repeatedly take any course with no remaining prerequisites'. It naturally produces an order too.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Which courses can you take right now? The ones with no prerequisites — i.e. indegree 0. What happens to their dependents after you take them?

2Hint 2Explore hint

Compute each node's indegree. Seed a queue with every indegree-0 node. Taking a course decrements its neighbours' indegrees; any that hit 0 are now takeable.

3Hint 3Explore hint

Count how many courses you manage to process. If a cycle exists, its nodes never reach indegree 0, so you'll process fewer than n — return processed == n.

A · Core idea

Kahn's algorithm peels the graph from its 'roots' inward.

Indegree = number of unmet prerequisites. A course with indegree 0 has nothing blocking it, so it can be taken immediately. We seed a queue with all such courses.

Taking a course unlocks its dependents. When we 'take' (dequeue) a course u, every course v that listed u as a prerequisite loses one blocker — decrement indegree[v]. If that drops v to 0, all of v's prerequisites are now satisfied, so we enqueue it. This ripples through the DAG layer by layer.

The cycle test is a simple count. Track how many courses we successfully process. In an acyclic graph every node eventually reaches indegree 0 and gets processed, so processed == numCourses. If there's a cycle, the nodes inside it perpetually block each other — none ever reaches indegree 0 — so the queue empties early and processed < numCourses. That comparison is the entire answer.

Bonus: it gives an order. The sequence in which we dequeue courses is a valid topological order. That's exactly what Course Schedule II asks for; here we only need the count, but it's worth mentioning to show depth.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Array state

initial

indeg of 0..3

course ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); int[] indeg = new int[numCourses]; for (int[] p : prerequisites) {Explore the full code

solution.javaJava

Kahn's Algorithm — Indegree BFS (Topological Sort) — reference

5 teaching notes

1
public boolean canFinish(int numCourses, int[][] prerequisites) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
4
    int[] indeg = new int[numCourses];
5
    for (int[] p : prerequisites) {
6
        // [a, b] means take b before a, so the edge points from prerequisite b to
7
        // dependent a.
8
        adj.get(p[1]).add(p[0]); // edge b -> a
9
        // a gains one unmet prerequisite; indegree counts how many courses must precede
10
        // it.
11
        indeg[p[0]]++;
12
    }
13
    Queue<Integer> q = new LinkedList<>();
14
    for (int i = 0; i < numCourses; i++) {
15
        // Courses with no prerequisites are takeable immediately — the BFS seeds.
16
        if (indeg[i] == 0) q.offer(i);
17
    }
18
    int processed = 0;
19
    while (!q.isEmpty()) {
20
        int u = q.poll();
21
        processed++;
22
        for (int v : adj.get(u)) {
23
            // Taking u satisfies one of v's prerequisites; when v hits 0 it becomes
24
            // takeable.
25
            if (--indeg[v] == 0) q.offer(v);
26
        }
27
    }
28
    // If a cycle existed, its nodes never reach indegree 0, so processed would fall
29
    // short.
30
    return processed == numCourses;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

Kahn's reframes 'is there a cycle?' as 'can I peel every node off by always removing something with no dependencies?'. A cycle is precisely a knot that can never be peeled — so a leftover count after peeling is the cycle's fingerprint.

ComplexityO(V + E) time, O(V + E) space — Building the adjacency list and indegrees is O(V + E). Each node is enqueued/dequeued once (O(V)) and each edge is relaxed once when its source is processed (O(E)). Total O(V + E); the graph and indegree arrays are O(V + E) space.

E · Edge cases and pitfalls6no prerequisites — All indegrees 0; every course enqueued and processed → true.Explore edge cases

Edge cases handled

no prerequisitesAll indegrees 0; every course enqueued and processed → true.
self-loop [0,0]indeg[0] = 1 forever; 0 never enqueues → processed < n → false.
two separate chainsDisconnected components both seeded by their indegree-0 roots → handled.

Pitfalls

Reversing the edge direction (a → b) — indegrees and the whole peel are wrong.
Forgetting to seed ALL indegree-0 nodes — disconnected components get stranded.
Comparing the produced order length loosely instead of `processed == numCourses`.

03.2

Approach 2 of 2 · Optimal

DFS with Three-Color Cycle Detection

TimeO(V + E)SpaceO(V + E)

Offer as the recursive alternative. Stress the three states — a plain visited set can't detect directed cycles.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A directed cycle means that while exploring a path you come back to a node that's still on the current path. How would you mark 'currently on the path'?

2Hint 2Explore hint

Use three states per node: 0 = unvisited, 1 = in-progress (on the current DFS path), 2 = fully done.

3Hint 3Explore hint

If DFS reaches an in-progress (state 1) node, that's a back edge → cycle → return false. Mark a node done (2) only after all its descendants are explored.

A · Core idea

Detect a cycle by watching for an edge back into the path we're currently on.

Why two states aren't enough. In an undirected graph a visited set suffices, but directed graphs need to distinguish 'visited on this path' from 'visited and finished'. Consider a diamond A→B, A→C, B→D, C→D: D is reached twice but there's no cycle. A 2-state set would falsely flag the second visit. We need to know whether the node we re-reach is still open on the current recursion stack.

Three colors. 0 = white (untouched), 1 = gray (in progress, on the current DFS path), 2 = black (finished, all descendants explored). When we start exploring a node we paint it gray; after recursing into all its children we paint it black.

The cycle rule. During DFS from node u, if we follow an edge to a node that is gray, we've found a back edge to an ancestor still on our path — a cycle — so return false. If it's black, it's a finished subtree with no cycle (like D in the diamond) and we can safely skip it.

Driver loops over all nodes. Because the graph may be disconnected, we launch DFS from every still-white node. If any DFS reports a cycle, the answer is false; otherwise all courses are completable.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numCourses = 2, prerequisites = [[1,0],[0,1]]

Interactive diagram

Back edge into a gray node = cycle

dfs(0)

Active call / nodeSupporting contextReturned stateNot active

0 and 1 are both gray (on the path) when the edge 1→0 is followed.

Final resultfalse

C · Code with teaching comments

solution.javaJava

DFS with Three-Color Cycle Detection — optimal

4 teaching notes

1
public boolean canFinish(int numCourses, int[][] prerequisites) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
4
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
5
    // Three states distinguish 'on the current path' from 'finished' — essential for
6
    // directed cycles.
7
    int[] color = new int[numCourses]; // 0 white, 1 gray, 2 black
8
    for (int i = 0; i < numCourses; i++) {
9
        if (color[i] == 0 && hasCycle(adj, color, i)) {
10
            return false;
11
        }
12
    }
13
    return true;
14
}
15
 
16
private boolean hasCycle(List<List<Integer>> adj, int[] color, int u) {
17
    // Mark the node open before exploring its descendants.
18
    color[u] = 1; // gray: on current path
19
    for (int v : adj.get(u)) {
20
        if (color[v] == 1) return true;            // back edge
21
        if (color[v] == 0 && hasCycle(adj, color, v)) return true;
22
    }
23
    // After all children done, close the node; future visits treat it as a safe
24
    // finished subtree.
25
    color[u] = 2; // black: fully explored
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

The gray state is the recursion stack made explicit: a node is gray exactly while it sits on the active call chain. A cycle is nothing more than an edge that points back up that chain — so 'edge to a gray node' is the precise, complete definition of a directed cycle.

ComplexityO(V + E) time, O(V + E) space — Each node is entered once and marked done; each edge is followed once. So O(V + E). Recursion depth and the state array are O(V); the adjacency list is O(V + E).

E · Edge cases and pitfalls6diamond 0→1,0→2,1→3,2→3 — 3 is reached twice but is black on the second visit → no false cycle → true.Explore edge cases

Edge cases handled

diamond 0→1,0→2,1→3,2→33 is reached twice but is black on the second visit → no false cycle → true.
self-loop [0,0]dfs(0) paints 0 gray, edge 0→0 sees gray → cycle → false.
disconnected DAGsDriver launches DFS from each white node; all finish black → true.

Pitfalls

Using a 2-state visited set — falsely flags re-reached finished nodes (the diamond) as cycles.
Marking a node done (black) before its descendants finish — misses real cycles.
Not resetting / not having a driver loop — disconnected components left unexplored.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>()); for (int[] p : prerequisites) adj.get(p[1]).add(p[0]); int[] color = new int[numCourses]; // 0 white, 1 gray, 2 blackExplore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Two-state visited misses/false-flags directed cycles

A boolean visited set can't tell 'on the current path' from 'already finished'. A node reached twice via different paths (a join) gets wrongly reported as a cycle.

Explore the code comparison

Don't write this

visited = set()
def dfs(u):
    if u in visited:
        return False  # WRONG: a finished join looks like a cycle
    visited.add(u)
    for v in adj[u]:
        if dfs(v): return True
    return False

Write this instead

color = [0] * n  # 0 white, 1 gray, 2 black
def dfs(u):
    color[u] = 1
    for v in adj[u]:
        if color[v] == 1: return True   # back edge
        if color[v] == 0 and dfs(v): return True
    color[u] = 2
    return False

Edge direction reversed

If [a, b] (take b before a) is stored as a → b, the indegrees count the wrong nodes and Kahn's seeds the wrong roots, producing incorrect feasibility.

Explore the code comparison

Don't write this

for (int[] p : prerequisites) {
    adj.get(p[0]).add(p[1]); // wrong: a -> b
    indeg[p[1]]++;
}

Write this instead

for (int[] p : prerequisites) {
    adj.get(p[1]).add(p[0]); // correct: b -> a
    indeg[p[0]]++;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Topological sort / cycle detection on a DAG (Kahn's BFS or DFS coloring)

Code pattern to memorize

# Kahn's:
indeg[v] for all v; queue all indeg==0
processed = 0
while queue: pop u; processed++;
    for nb in adj[u]: indeg[nb]--; if 0: push nb
return processed == numCourses

Rules to remember

1Pick a consistent edge direction and stick to it: here [a, b] means b is a prerequisite of a, so the edge is b → a.
2Kahn's: count processed nodes. If fewer than n are processed, a cycle trapped the rest → impossible.
3DFS: use three states (unvisited / in-progress / done). Hitting an in-progress node = back edge = cycle.
4A two-state visited set is NOT enough for directed cycle detection — you need the in-progress (gray) state.
5If the problem asks for the order, output the Kahn's pop sequence (Course Schedule II); here we only need yes/no.

Use this pattern when

Prerequisite / dependency ordering ('finish all', 'valid build order')
Detecting cycles in a directed graph
Scheduling tasks with 'must come before' constraints
Linearising a DAG (compilation order, package install order)

Choose another pattern when

Undirected cycle detection → Union-Find or simple DFS-with-parent (Graph Valid Tree)
Need shortest path, not ordering → BFS/Dijkstra
Weighted dependencies / critical path → longest-path DP on the DAG

Interview takeaway

Course Schedule is topological sort in disguise: 'can I finish everything?' = 'is the dependency graph acyclic?'. Kahn's indegree BFS and DFS three-color marking are the two canonical answers. The same template solves Course Schedule II, Alien Dictionary, and build-order questions.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTopological sort / directed cycle detection. Kahn's indegree BFS and DFS three-color marking both run in O(V+E); Kahn's also yields a valid order. Same family as Course Schedule II, Alien Dictionary, and Parallel Courses.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Course Schedule II
Return the actual topological order — output Kahn's pop sequence (empty if a cycle exists).
Alien Dictionary
Coming soon
Derive ordering constraints from adjacent words, then topologically sort the letters.
Minimum Height Trees
Coming soon
Peel leaves layer by layer (a Kahn's-style trim) until 1–2 centroids remain.
Parallel Courses
Coming soon
Topological sort by levels; the number of BFS layers is the minimum semesters.

Same pattern

←

Number of Islands

Continue · Next problem

Clone Graph

mediumGraphsLC #207Asked very often

Course Schedule (Topological Sort)

LCPractice

Graphs · 2 of 34 · 11 min

Return true if you can finish all courses. Otherwise, return false.

In plain English

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Note: Edge 0 → 1: take 0 then 1. No cycle, so all courses are completable.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Note: Edges 0 → 1 and 1 → 0 form a cycle; neither course can start first.

Example 3

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Note: 0 → 1, 0 → 2, 1 → 3, 2 → 3 is a DAG; a valid order is 0,1,2,3.

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000
prerequisites[i].length == 2
0 ≤ aᵢ, bᵢ < numCourses
All the pairs prerequisites[i] are distinct

Clarifying questions4First question: Which way does the edge point — from prerequisite or to it?Explore questions

Q1.Which way does the edge point — from prerequisite or to it?
[a, b] means b is required before a, so I'll draw b → a. I confirm direction explicitly because reversing it silently breaks the indegree logic.
Q2.Can there be duplicate or self-loop prerequisites?
Pairs are distinct per constraints. A self-loop [a, a] would be an immediate cycle → false; I'd handle it naturally since it gives a node indegree it can never clear.
Q3.Do I need the actual order or just feasibility?
Just true/false here. If the order were required, that's Course Schedule II — I'd emit Kahn's pop sequence.
Q4.Could the graph be disconnected?
Yes — multiple independent course clusters. Kahn's handles that automatically by seeding all indegree-0 nodes; DFS must loop over every unvisited node.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you translate prerequisites into a directed graph with a consistent edge direction, and whether you know that 'can finish' reduces to 'is acyclic' — solved by topological sort.

Where candidates slip

Reversing the edge direction, using a 2-state visited set for directed cycle detection (misses back edges), or building the graph but never checking for the cycle.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Kahn's Algorithm — Indegree BFS (Topological Sort)	`O(V + E)`	`O(V + E)`	The go-to answer. Phrase it as 'repeatedly take any course with no remaining prerequisites'. It naturally produces an order too.	Read
2	DFS with Three-Color Cycle DetectionOptimal	`O(V + E)`	`O(V + E)`	Offer as the recursive alternative. Stress the three states — a plain visited set can't detect directed cycles.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Kahn's Algorithm — Indegree BFS (Topological Sort)

TimeO(V + E)SpaceO(V + E)

The go-to answer. Phrase it as 'repeatedly take any course with no remaining prerequisites'. It naturally produces an order too.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Which courses can you take right now? The ones with no prerequisites — i.e. indegree 0. What happens to their dependents after you take them?

2Hint 2Explore hint

Compute each node's indegree. Seed a queue with every indegree-0 node. Taking a course decrements its neighbours' indegrees; any that hit 0 are now takeable.

3Hint 3Explore hint

Count how many courses you manage to process. If a cycle exists, its nodes never reach indegree 0, so you'll process fewer than n — return processed == n.

A · Core idea

Kahn's algorithm peels the graph from its 'roots' inward.

Indegree = number of unmet prerequisites. A course with indegree 0 has nothing blocking it, so it can be taken immediately. We seed a queue with all such courses.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Array state

initial

indeg of 0..3

course ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Kahn's Algorithm — Indegree BFS (Topological Sort) — reference

5 teaching notes

1
public boolean canFinish(int numCourses, int[][] prerequisites) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
4
    int[] indeg = new int[numCourses];
5
    for (int[] p : prerequisites) {
6
        // [a, b] means take b before a, so the edge points from prerequisite b to
7
        // dependent a.
8
        adj.get(p[1]).add(p[0]); // edge b -> a
9
        // a gains one unmet prerequisite; indegree counts how many courses must precede
10
        // it.
11
        indeg[p[0]]++;
12
    }
13
    Queue<Integer> q = new LinkedList<>();
14
    for (int i = 0; i < numCourses; i++) {
15
        // Courses with no prerequisites are takeable immediately — the BFS seeds.
16
        if (indeg[i] == 0) q.offer(i);
17
    }
18
    int processed = 0;
19
    while (!q.isEmpty()) {
20
        int u = q.poll();
21
        processed++;
22
        for (int v : adj.get(u)) {
23
            // Taking u satisfies one of v's prerequisites; when v hits 0 it becomes
24
            // takeable.
25
            if (--indeg[v] == 0) q.offer(v);
26
        }
27
    }
28
    // If a cycle existed, its nodes never reach indegree 0, so processed would fall
29
    // short.
30
    return processed == numCourses;
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6no prerequisites — All indegrees 0; every course enqueued and processed → true.Explore edge cases

Edge cases handled

no prerequisitesAll indegrees 0; every course enqueued and processed → true.
self-loop [0,0]indeg[0] = 1 forever; 0 never enqueues → processed < n → false.
two separate chainsDisconnected components both seeded by their indegree-0 roots → handled.

Pitfalls

Reversing the edge direction (a → b) — indegrees and the whole peel are wrong.
Forgetting to seed ALL indegree-0 nodes — disconnected components get stranded.
Comparing the produced order length loosely instead of `processed == numCourses`.

03.2

Approach 2 of 2 · Optimal

DFS with Three-Color Cycle Detection

TimeO(V + E)SpaceO(V + E)

Offer as the recursive alternative. Stress the three states — a plain visited set can't detect directed cycles.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A directed cycle means that while exploring a path you come back to a node that's still on the current path. How would you mark 'currently on the path'?

2Hint 2Explore hint

Use three states per node: 0 = unvisited, 1 = in-progress (on the current DFS path), 2 = fully done.

3Hint 3Explore hint

If DFS reaches an in-progress (state 1) node, that's a back edge → cycle → return false. Mark a node done (2) only after all its descendants are explored.

A · Core idea

Detect a cycle by watching for an edge back into the path we're currently on.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

numCourses = 2, prerequisites = [[1,0],[0,1]]

Interactive diagram

Back edge into a gray node = cycle

dfs(0)

Active call / nodeSupporting contextReturned stateNot active

0 and 1 are both gray (on the path) when the edge 1→0 is followed.

Final resultfalse

C · Code with teaching comments

solution.javaJava

DFS with Three-Color Cycle Detection — optimal

4 teaching notes

1
public boolean canFinish(int numCourses, int[][] prerequisites) {
2
    List<List<Integer>> adj = new ArrayList<>();
3
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
4
    for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
5
    // Three states distinguish 'on the current path' from 'finished' — essential for
6
    // directed cycles.
7
    int[] color = new int[numCourses]; // 0 white, 1 gray, 2 black
8
    for (int i = 0; i < numCourses; i++) {
9
        if (color[i] == 0 && hasCycle(adj, color, i)) {
10
            return false;
11
        }
12
    }
13
    return true;
14
}
15
 
16
private boolean hasCycle(List<List<Integer>> adj, int[] color, int u) {
17
    // Mark the node open before exploring its descendants.
18
    color[u] = 1; // gray: on current path
19
    for (int v : adj.get(u)) {
20
        if (color[v] == 1) return true;            // back edge
21
        if (color[v] == 0 && hasCycle(adj, color, v)) return true;
22
    }
23
    // After all children done, close the node; future visits treat it as a safe
24
    // finished subtree.
25
    color[u] = 2; // black: fully explored
26
    return false;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6diamond 0→1,0→2,1→3,2→3 — 3 is reached twice but is black on the second visit → no false cycle → true.Explore edge cases

Edge cases handled

diamond 0→1,0→2,1→3,2→33 is reached twice but is black on the second visit → no false cycle → true.
self-loop [0,0]dfs(0) paints 0 gray, edge 0→0 sees gray → cycle → false.
disconnected DAGsDriver launches DFS from each white node; all finish black → true.

Pitfalls

Using a 2-state visited set — falsely flags re-reached finished nodes (the diamond) as cycles.
Marking a node done (black) before its descendants finish — misses real cycles.
Not resetting / not having a driver loop — disconnected components left unexplored.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Two-state visited misses/false-flags directed cycles

A boolean visited set can't tell 'on the current path' from 'already finished'. A node reached twice via different paths (a join) gets wrongly reported as a cycle.

Explore the code comparison

Don't write this

visited = set()
def dfs(u):
    if u in visited:
        return False  # WRONG: a finished join looks like a cycle
    visited.add(u)
    for v in adj[u]:
        if dfs(v): return True
    return False

Write this instead

color = [0] * n  # 0 white, 1 gray, 2 black
def dfs(u):
    color[u] = 1
    for v in adj[u]:
        if color[v] == 1: return True   # back edge
        if color[v] == 0 and dfs(v): return True
    color[u] = 2
    return False

Edge direction reversed

If [a, b] (take b before a) is stored as a → b, the indegrees count the wrong nodes and Kahn's seeds the wrong roots, producing incorrect feasibility.

Explore the code comparison

Don't write this

for (int[] p : prerequisites) {
    adj.get(p[0]).add(p[1]); // wrong: a -> b
    indeg[p[1]]++;
}

Write this instead

for (int[] p : prerequisites) {
    adj.get(p[1]).add(p[0]); // correct: b -> a
    indeg[p[0]]++;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Topological sort / cycle detection on a DAG (Kahn's BFS or DFS coloring)

Code pattern to memorize

# Kahn's:
indeg[v] for all v; queue all indeg==0
processed = 0
while queue: pop u; processed++;
    for nb in adj[u]: indeg[nb]--; if 0: push nb
return processed == numCourses

Rules to remember

1Pick a consistent edge direction and stick to it: here [a, b] means b is a prerequisite of a, so the edge is b → a.
2Kahn's: count processed nodes. If fewer than n are processed, a cycle trapped the rest → impossible.
3DFS: use three states (unvisited / in-progress / done). Hitting an in-progress node = back edge = cycle.
4A two-state visited set is NOT enough for directed cycle detection — you need the in-progress (gray) state.
5If the problem asks for the order, output the Kahn's pop sequence (Course Schedule II); here we only need yes/no.

Use this pattern when

Prerequisite / dependency ordering ('finish all', 'valid build order')
Detecting cycles in a directed graph
Scheduling tasks with 'must come before' constraints
Linearising a DAG (compilation order, package install order)

Choose another pattern when

Undirected cycle detection → Union-Find or simple DFS-with-parent (Graph Valid Tree)
Need shortest path, not ordering → BFS/Dijkstra
Weighted dependencies / critical path → longest-path DP on the DAG

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Course Schedule II
Return the actual topological order — output Kahn's pop sequence (empty if a cycle exists).
Alien Dictionary
Coming soon
Derive ordering constraints from adjacent words, then topologically sort the letters.
Minimum Height Trees
Coming soon
Peel leaves layer by layer (a Kahn's-style trim) until 1–2 centroids remain.
Parallel Courses
Coming soon
Topological sort by levels; the number of BFS layers is the minimum semesters.

Same pattern

←

Number of Islands

Continue · Next problem

Clone Graph