There are numCourses courses labelled 0 to numCourses - 1. You are given a list prerequisites where prerequisites[i] = [a, b] means you must take course b before course a.
Return true if it is possible to finish all the courses, and false otherwise.
It is possible to finish exactly when the prerequisite relation contains no cycle — a cycle would mean a course is, transitively, its own prerequisite.
Example
Take 0, then 1 — no cycle, so all courses can be finished.
Constraints
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= a, b < numCourses
- All the pairs prerequisites[i] are distinct.
Intuition
We can finish all the courses exactly when their prerequisite graph has no cycle — a cycle means a course is, transitively, its own prerequisite. The brute-force way to detect a cycle is to launch a DFS from every node and, on each path, check whether we ever revisit a node already on the current path.
function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prerequisites) adj[b].push(a); // edge b → a (b unlocks a)
// Does any path out of `node` loop back onto the current stack?
const hasCycle = (node, onStack) => {
if (onStack.has(node)) return true; // revisited a node on this path → cycle
onStack.add(node);
for (const next of adj[node])
if (hasCycle(next, onStack)) return true;
onStack.delete(node); // leave the path on the way back up
return false;
};
for (let c = 0; c < numCourses; c++)
if (hasCycle(c, new Set())) return false;
return true;
}Restarting a fresh DFS from every course re-explores shared subgraphs over and over. Can we do better?
The key observation: cycle detection over a directed graph is exactly what a topological sort does as a by-product. Build the graph with an edge b → a for each prerequisite [a, b], and use Kahn's algorithm: compute each course's in-degree (number of unmet prerequisites), start a queue with every in-degree-0 course, and repeatedly take a ready course, decrementing the in-degree of everything it unlocks. Courses caught in a cycle never reach in-degree 0, so if fewer than numCourses come out of the queue, a cycle blocked them — return false. One O(V + E) pass, no restarts.
A dependency graph has no faithful lane animation. The static graph below is the acyclic case; the dashed intuition: peel off in-degree-0 nodes layer by layer until either the graph empties (no cycle) or stalls (cycle).
- Edge direction is the whole problem.
[a, b]means b before a, so the unlock edge isb → a. Reverse it and a finishable curriculum reports a cycle and vice-versa. - Count, don't inspect. You never need the actual ordering — just whether the number of courses dequeued equals
numCourses. A shortfall is precisely the set of cycle-trapped courses.
Optimization
Kahn's algorithm (BFS topological sort)
Model the courses as a directed graph: an edge b -> a for each prerequisite [a, b] ("b unlocks a"). The courses can all be finished iff this graph has no directed cycle, which a topological sort detects directly.
Compute each course's in-degree (how many prerequisites it still has). Repeatedly take any course with in-degree 0 — it is ready to take — and "remove" it by decrementing the in-degree of every course it unlocks, queuing any that drop to 0. Count how many courses get taken this way. If a cycle exists, the courses inside it can never reach in-degree 0, so the count falls short of numCourses.
O(V + E) time — every course and prerequisite edge is processed once — and O(V + E) space for the adjacency lists and the queue.
function canFinish(numCourses, prerequisites) {
// adj[b] lists the courses that b unlocks; indegree[a] counts a's remaining prerequisites.
const adj = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
adj[b].push(a);
indegree[a]++;
}
// Start with every course that has no outstanding prerequisite.
const queue = [];
for (let c = 0; c < numCourses; c++) {
if (indegree[c] === 0) queue.push(c);
}
let taken = 0;
while (queue.length > 0) {
const course = queue.shift();
taken++; // this course is now ready and "taken"
for (const next of adj[course]) {
// One prerequisite of next is satisfied; if that was its last, it's ready.
if (--indegree[next] === 0) queue.push(next);
}
}
// Every course taken means no cycle blocked us.
return taken === numCourses;
}Complexity analysis
Time complexity: O(V + E). Here's why:
- Building the adjacency lists and in-degrees is one pass over the
Eprerequisite edges plusVcourses. - Kahn's algorithm dequeues each course once and decrements once per outgoing edge.
Every course and edge is handled a constant number of times — O(V + E), where V = numCourses and E = prerequisites.length.
Space complexity: O(V + E). Here's why:
- The adjacency lists hold all
Eedges; the in-degree array and queue areO(V).
So the extra space is O(V + E).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| numCourses = 1, prerequisites = [] | true | One course, no prerequisites — finishable. |
| numCourses = 3prerequisites = 10 21 | true | A clean chain 0 → 1 → 2 — finishable. |
| numCourses = 3prerequisites = 01 12 20 | false | A 3-cycle — every course is transitively its own prerequisite. |
| numCourses = 5prerequisites = 10 20 30 40 | true | Fan-out from course 0 — many dependents, no cycle. |
| numCourses = 4prerequisites = 10 21 02 | false | A cycle 0 → 1 → 2 → 0 traps three courses; course 3 alone can't rescue it. |
Try it yourself
Write your solution against the real judge before checking the reference.