Course Schedule
Decide whether every course can be finished, by counting how many Kahn's algorithm can take before a prerequisite cycle stops it.
Examples
Take course 0, then course 1.
Each course needs the other first, so neither can ever be taken.
Problem Understanding
There are numCourses courses labeled 0 to numCourses - 1. You are given prerequisites array where [a, b] means taking course b is mandatory before a.
Return true if you can finish all courses, false otherwise (i.e., if there is a cycle).
Strategy (Kahn's Algorithm)
A course can be taken once all of its prerequisites have been. Count down to that moment for every course:
Turn each pair
[course, prereq]into an edgeprereq → course, and count each course's prerequisites (its in-degree).Queue every course whose count is 0 — nothing stands in its way.
Take the front course and add one to taken; each course it unlocks loses one prerequisite, and any that reaches 0 joins the queue.
When the queue is empty, every course can be finished exactly when taken == numCourses. A course on a prerequisite cycle — or after one — never reaches 0.
Interactive Visualization
Each arrow runs from a prerequisite to the course it unlocks — the pair [1, 0] is drawn 0 → 1. The number above a course is how many of its prerequisites are still untaken.
Watch the taken counter beside the figure: every course that leaves the queue adds one. The answer is nothing more than whether it reaches numCourses. Try Blocked — courses 0 and 4 are taken, then the queue runs dry with 1, 2 and 3 in red: 1 and 2 need each other, and 3 needs 2.
Dry Run
The figure's default: numCourses = 5, prerequisites = [[1,0],[2,1],[3,1],[4,3],[4,2]]. Prerequisite counts start as [0, 1, 1, 1, 2].
| # | Queue | Take | Unlocks | Taken |
|---|---|---|---|---|
| 1 | [0] |
0 | 1: 1→0 — queue it | 1 |
| 2 | [1] |
1 | 2: 1→0, 3: 1→0 — queue both | 2 |
| 3 | [2, 3] |
2 | 4: 2→1 | 3 |
| 4 | [3] |
3 | 4: 1→0 — queue it | 4 |
| 5 | [4] |
4 | — | 5 |
The queue is empty and taken = 5 = numCourses: return true.
With [[1,0],[0,1]] (LeetCode example 2) both counts start at 1, the queue starts empty, and taken stays 0: return false.
Solution
Kahn's algorithm in all six languages — the lines light up as the figure above steps.
Course Schedule Code
1var canFinish = function(numCourses, prerequisites) {2 const graph = Array.from({ length: numCourses }, () => []);3 const indegree = new Array(numCourses).fill(0);4 for (const [course, prereq] of prerequisites) {5 graph[prereq].push(course);6 indegree[course]++;7 }89 const queue = [];10 for (let c = 0; c < numCourses; c++) {11 if (indegree[c] === 0) queue.push(c);12 }13 let taken = 0;14 let head = 0;15 while (head < queue.length) {16 const course = queue[head++];17 taken++;18 for (const unlocked of graph[course]) {19 indegree[unlocked]--;20 if (indegree[unlocked] === 0) queue.push(unlocked);21 }22 }2324 return taken === numCourses;25};
Edge Cases & Common Mistakes
Watch out for:
Direction:
[a, b]means b comes first, so the edge isb → aand it isawhose count goes up. Building it the other way round still finds cycles, but the counts describe the wrong courses.Disconnected courses: fine. Every course with no prerequisites starts in the queue, whichever group it belongs to.
No prerequisites at all: every course starts in the queue and the answer is
true.Cycle: if the queue empties with taken <
numCourses, returnfalse. The untaken courses are on a cycle or wait on one.