Course Schedule II: Topological Sort With Kahn's Algorithm
Solve Course Schedule II with Kahn's algorithm — build in-degrees, BFS the dependency graph, detect cycles, and return a valid course order in O(V+E).
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a semester's worth of courses, and some can't be taken until you've cleared their prerequisites. Course Schedule II asks the practical version of that headache: give me an actual order I can register in, or tell me it's impossible because the prerequisites loop back on themselves.
Underneath the story is one of the most reusable graph patterns in interviews: topological sort. Any time you have tasks with "this before that" constraints — build systems, package installs, spreadsheet recalculation, course plans — you're ordering the nodes of a directed graph so every edge points forward. Kahn's algorithm does it in a single linear pass and catches cycles for free.
The problem
You're given numCourses labeled 0 to numCourses - 1, and a list prerequisites where each pair [a, b] means you must take course b before course a. Return any valid order in which to take all courses. If no valid order exists (the prerequisites contain a cycle), return an empty array [].
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]
Reading the edges:
[1,0] -> take 0 before 1
[2,0] -> take 0 before 2
[3,1] -> take 1 before 3
[3,2] -> take 2 before 3Course 0 unlocks 1 and 2; both feed into 3. So 0 has to come first and 3 has to come last. [0, 2, 1, 3] would be equally valid — any order that respects every arrow is accepted.
Two subtleties shape the solution. First, the pair [a, b] reads backwards from how you'd say it out loud — the dependency b is the second element. Second, there can be more than one correct answer, so the algorithm just needs to produce a valid order, not a specific one.
The brute force baseline
The direct idea: repeatedly find a course with no unmet prerequisites, take it, cross it off everyone's list, and repeat until you're stuck or done.
function findOrder(numCourses, prerequisites) {
const remaining = new Set(Array.from({ length: numCourses }, (_, i) => i));
const ordering = [];
while (remaining.size > 0) {
// Rescan every course looking for one with all prereqs already taken.
const next = [...remaining].find((c) =>
prerequisites.every(([course, prereq]) => course !== c || !remaining.has(prereq))
);
if (next === undefined) return []; // nothing takeable -> cycle
ordering.push(next);
remaining.delete(next);
}
return ordering;
}It works, but it re-answers the same question every round. Each pass over remaining scans the entire prerequisites list for every still-unfinished course. With V courses and E prerequisites that's roughly O(V² + V·E) — for a chain of a few thousand courses it grinds. The waste is structural: after taking a course, only the courses that directly depended on it could have changed, yet we re-examine all of them.
The key insight: count prerequisites, don't re-scan them
Instead of asking "which course is takeable?" over and over, track a single number per course: its in-degree — how many prerequisites it still has left. A course with in-degree 0 is takeable right now.
The trick is maintaining those counters incrementally. When you take a course, you don't rescan anything — you just walk that course's outgoing edges and decrement each neighbor's in-degree by one. Any neighbor that drops to 0 just became takeable, so you park it in a queue.
That's Kahn's algorithm: seed a queue with every in-degree-0 course, then repeatedly dequeue one, append it to the order, and decrement its neighbors. The queue always holds exactly the courses that are ready to go. And the cycle check falls out naturally — if a set of courses depends on each other in a loop, none of them ever reaches in-degree 0, so they never enter the queue. Count what you managed to order: fewer than numCourses means a cycle trapped the rest.
The optimal solution
This mirrors the exact algorithm the Course Schedule II visualizer steps through — same inDegree array, adjList, queue, and ordering.
function findOrder(numCourses, prerequisites) {
const inDegree = new Array(numCourses).fill(0);
const adjList = Array.from({ length: numCourses }, () => []);
// Build graph and calculate in-degrees.
for (const [course, prereq] of prerequisites) {
adjList[prereq].push(course); // prereq -> course
inDegree[course]++;
}
// Seed the queue with every course that has no prerequisites.
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i);
}
const ordering = [];
// Kahn's algorithm (topological sort via BFS).
while (queue.length > 0) {
const curr = queue.shift();
ordering.push(curr);
// "Remove" curr's outgoing edges.
for (const neighbor of adjList[curr]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
// Full ordering means success; short ordering means a cycle blocked it.
return ordering.length === numCourses ? ordering : [];
}Watch the edge direction in the build loop: adjList[prereq].push(course) points from the prerequisite to the course that needs it. That's what makes "take curr, then relax the things that depend on it" work when you decrement inDegree[neighbor].
Walkthrough
Trace numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]].
After the build loop, the state is:
adjList: 0 -> [1, 2] 1 -> [3] 2 -> [3] 3 -> []
inDegree: [0, 1, 1, 2] // course 3 needs both 1 and 2Only course 0 has in-degree 0, so the queue starts as [0]. Now the BFS loop, one dequeue per row:
| Step | curr (dequeued) | ordering | neighbors relaxed | inDegree after | queue after |
|---|---|---|---|---|---|
| 1 | 0 | [0] | 1→0, 2→0 (both freed) | [0,0,0,2] | [1, 2] |
| 2 | 1 | [0,1] | 3→1 (still blocked) | [0,0,0,1] | [2] |
| 3 | 2 | [0,1,2] | 3→0 (freed) | [0,0,0,0] | [3] |
| 4 | 3 | [0,1,2,3] | none | [0,0,0,0] | [] |
The interesting row is Step 2. Course 3 depends on both 1 and 2, so when 1 is taken its in-degree only drops from 2 to 1 — still blocked. It's not until Step 3, after 2 is also taken, that 3 hits 0 and enters the queue. That "wait for all prerequisites" behavior is exactly what the in-degree counter buys you.
The loop ends with ordering.length === 4 === numCourses, so the answer is [0, 1, 2, 3]. Had the input been [[0,1],[1,2],[2,0]] — a 3-course cycle — no course would ever start at in-degree 0, the queue would begin empty, and ordering would stay [], correctly reporting "impossible."
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Repeated rescan | O(V² + V·E) | O(V) | re-checks every prerequisite each round |
| Kahn's algorithm | O(V + E) | O(V + E) | each node dequeued once, each edge relaxed once |
V is the number of courses, E the number of prerequisite pairs. Building the graph touches every edge once (O(E)) and every node once (O(V)). In the BFS, each course is enqueued and dequeued exactly one time, and each edge is decremented exactly one time when its source is processed — so the whole traversal is O(V + E). Space is the adjacency list (O(V + E)) plus the in-degree array and queue (O(V)).
Common mistakes
- Reversing the edge.
[a, b]meansbbeforea. The edge goesprereq → course, i.e.adjList[b].push(a)andinDegree[a]++. Flip it and you'll produce a reversed order or a phantom cycle. - Forgetting the length check at the end. Without
ordering.length === numCourses, a cyclic input silently returns a partial order that looks valid but skips the trapped courses. The count is the cycle detector. - Only seeding the queue with course
0. Multiple courses can start with in-degree0(independent tracks). You must scan allnumCoursesand enqueue every zero. - Decrementing an in-degree twice. Only decrement when you process a node's outgoing edges — once per edge. Re-relaxing a neighbor you already handled corrupts the counts and can wrongly free a course early.
- Ignoring courses with no prerequisites at all. Every course from
0tonumCourses - 1must appear in the output, even ones that show up nowhere inprerequisites. Initializing the arrays bynumCourses(not by the prerequisites list) handles this.
Where this pattern shows up next
Kahn's algorithm is one flavor of graph traversal; the in-degree bookkeeping is specific to topological ordering, but the BFS skeleton and cycle-reasoning transfer widely:
- Max Area of Island — flood-fill BFS/DFS over a grid graph, counting connected components instead of ordering them.
- Find if Path Exists in Graph — the reachability question a topological order implicitly answers.
- All Paths From Source to Target — enumerating every route through a DAG, the same directed-acyclic structure Course Schedule II assumes.
- Redundant Connection — cycle detection again, this time in an undirected graph via union-find rather than in-degrees.
You can also step through Course Schedule II interactively to watch in-degrees tick down and courses drop into the queue the moment they're freed.
FAQ
Why does Course Schedule II use BFS instead of DFS?
Both work — topological sort has a DFS variant that pushes nodes onto a stack in post-order and reverses it. Kahn's BFS approach is often preferred here because cycle detection is dead simple: if the final ordering is shorter than numCourses, a cycle exists, no extra visited-state coloring needed. BFS also processes courses in a natural "all currently-available options first" order, which maps cleanly onto the queue of in-degree-0 courses.
How does the in-degree count detect a cycle?
A course only enters the queue when its in-degree reaches 0, meaning every prerequisite has been taken. In a cycle, each course in the loop is waiting on another course in the same loop, so none of their in-degrees ever hit 0 — they're stuck holding each other up. The queue drains without ever touching them, so ordering ends up shorter than numCourses. Comparing the two lengths is the entire cycle test.
What time complexity does Kahn's algorithm run in?
O(V + E), where V is the number of courses and E is the number of prerequisite pairs. Building the adjacency list and in-degree array is O(V + E), and the BFS visits each course once and relaxes each edge once. Space is also O(V + E) for the adjacency list, plus O(V) for the in-degree array and queue. That linear bound is the whole reason to prefer it over the repeated-rescan baseline.
Can there be more than one valid answer?
Yes. Whenever multiple courses sit in the queue at once — independent tracks with no dependency between them — the order you dequeue them in is arbitrary and every choice yields a valid topological order. For the sample input, both [0, 1, 2, 3] and [0, 2, 1, 3] are correct. LeetCode accepts any valid ordering, so you don't need to match a specific one; you just need one that respects every prerequisite edge.
What's the difference between Course Schedule and Course Schedule II?
Course Schedule (the first version) only asks whether a valid order exists — it returns a boolean. Course Schedule II asks you to actually produce the order, returning the array (or [] if impossible). The algorithm is identical up to the final step: Course Schedule I just checks whether you managed to process all numCourses, while Course Schedule II returns the ordering array you built along the way.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.