Course Schedule
The Prompt
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] = [ai, bi]` indicates that you must take course `bi` first if you want to take course `ai`. Return `true` if you can finish all courses. Otherwise, return `false`.
Understanding the Problem
Model courses as nodes in a directed graph: prerequisite pair [a, b] means "take b before a", an edge b → a. The question "can you finish all courses?" becomes "is this graph free of cycles?" — a cycle is a circular dependency no ordering can satisfy.
Kahn's algorithm answers it constructively. Track each course's in-degree (how many unmet prerequisites it has). Repeatedly take any course with in-degree 0 — it is free to take right now — and remove its outgoing edges, which may free up other courses. If this process takes every course, an order exists; if it stalls with courses left over, those leftovers form or depend on a cycle.
The Interview Flow
Interviewer
You're given a number of courses and a list of prerequisites. How do you determine if it's possible to take all the courses?
Candidate
This can be modeled as a directed graph. Each course is a node, and a prerequisite `[a, b]` (must take b for a) is a directed edge from `b` to `a`. The question is asking if this graph has any cycles.
Interviewer
Why is a cycle a problem?
Candidate
A cycle means there's a circular dependency. For example, if Course 1 requires Course 2, and Course 2 requires Course 1, it's impossible to complete them. So, if the graph has a cycle, I should return false. If it's a Directed Acyclic Graph (DAG), I return true.
Interviewer
How do you detect a cycle in a directed graph?
Candidate
I can use Depth-First Search. I need to keep track of the nodes I'm currently visiting in my current recursion path. I can use a set for this, let's call it `visiting`. When I start a DFS for a node, I add it to `visiting`. If, during the traversal, I encounter a neighbor that is already in `visiting`, I have found a back edge, which means there is a cycle.
Interviewer
What other state do you need to track?
Candidate
I also need a `visited` set for all nodes that have been part of a completed DFS traversal. This is an optimization to avoid re-processing nodes whose subgraphs are already known to be cycle-free. So, the process for a DFS on a node is: add to `visiting`, recurse on neighbors. If a neighbor is in `visiting`, we found a cycle. After all neighbors are explored, remove from `visiting` and add to `visited`.
Interviewer
That's a complete cycle detection algorithm. Please implement it.
Why does "processed count equals numCourses" decide the answer?
The invariant: a course enters the queue only when all of its prerequisites have already been processed, so the order in which courses leave the queue is a valid schedule. Every course in a cycle waits forever on another cycle member, so its in-degree never reaches 0 and it is never processed — cyclic graphs always come up short.
Each node is queued once and each edge is removed once: O(V + E) time, O(V + E) space for the adjacency list and in-degree table. The DFS-coloring alternative has the same bounds; Kahn's is often easier to defend in an interview because it produces the actual order.
Cycle Detection using DFS
- First, build an adjacency list representation of the graph from the `prerequisites` array.
- Initialize two sets: `visited` (to keep track of all nodes that have been completely processed) and `visiting` (to keep track of nodes in the current recursive path).
- Iterate through all courses from 0 to `numCourses - 1`. For each course, call a `dfs` helper function.
- If the `dfs` function ever returns `false`, it means a cycle was detected, so we can immediately return `false`.
- **DFS Helper `dfs(course)`:**
- Add `course` to the `visiting` set.
- For each `neighbor` in the adjacency list of the `course`:
- If `neighbor` is in the `visiting` set, we have found a back edge, so a cycle exists. Return `false`.
- Recursively call `dfs(neighbor)`. If this call returns `false`, propagate it up by returning `false`.
- Once all neighbors have been explored without finding a cycle, remove `course` from `visiting` and add it to `visited`.
- Return `true` to indicate this path is cycle-free.
- If the main loop completes, it means no cycles were found in any component of the graph. Return `true`.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function canFinish(numCourses, prerequisites) {
const adjList = new Array(numCourses).fill(0).map(() => []);
for (const [course, prereq] of prerequisites) {
adjList[prereq].push(course);
}
const visited = new Set();
const visiting = new Set();
function hasCycle(course) {
visiting.add(course);
for (const neighbor of adjList[course]) {
if (visiting.has(neighbor)) {
return true; // Cycle detected
}
if (!visited.has(neighbor)) {
if (hasCycle(neighbor)) {
return true;
}
}
}
visiting.delete(course);
visited.add(course);
return false;
}
for (let i = 0; i < numCourses; i++) {
if (!visited.has(i)) {
if (hasCycle(i)) {
return false;
}
}
}
return true;
}Explanation
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] — course 0 unlocks 1 and 2, which together unlock 3.
1The dependency graph with in-degrees: course 0 needs nothing (in-degree 0), courses 1 and 2 each need one course, course 3 needs two. Only course 0 starts in the queue.
2Process course 0 and remove its edges: the in-degrees of 1 and 2 both drop to 0, so both join the queue. Course 3 still waits on two prerequisites.
3Process 1 and 2 — each removal drops course 3's in-degree by one, reaching 0 — then process 3. All 4 courses processed = numCourses, so return true; one valid order is 0, 1, 2, 3.
Complexity Analysis
TIME
O(V + E)
SPACE
O(V + E)
Finished working through this one?
Mark it complete to track it on your Data Structures path.