207. Course Schedule
mediumAsked at DoorDashGiven courses and prerequisites, determine if you can finish all courses. DoorDash uses this to test cycle detection in directed graphs — they want either DFS with white/gray/black coloring or Kahn's BFS topological sort.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DoorDash loops.
- Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Course Schedule as a recurring graph + topological-sort question.
- Blind (2025-11)— DoorDash backend SDE reports list this as a common dependency-graph framing.
Problem
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_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return true if you can finish all courses. Otherwise, return false.
Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a_i, b_i < numCoursesAll the pairs prerequisites[i] are unique.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]]trueExplanation: Take course 0 first then course 1.
Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseExplanation: Cycle: 0 depends on 1, 1 depends on 0.
Approaches
1. Kahn's algorithm (BFS topological sort)
Compute in-degree per node. Enqueue all 0-in-degree nodes. Pop one, decrement neighbors' in-degree, enqueue neighbors that hit 0. If we pop numCourses, no cycle.
- Time
- O(V + E)
- Space
- O(V + E)
function canFinish(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [a, b] of prerequisites) {
graph[b].push(a);
indegree[a]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) queue.push(i);
}
let processed = 0;
while (queue.length) {
const node = queue.shift();
processed++;
for (const next of graph[node]) {
indegree[next]--;
if (indegree[next] === 0) queue.push(next);
}
}
return processed === numCourses;
}Tradeoff: DoorDash's preferred answer. Pure BFS, iterative — no recursion stack to worry about for huge graphs. Easy to extend to Course Schedule II (returning the order).
2. DFS with three-color cycle detection
DFS each unvisited node. Use 0/1/2 coloring: 0=unvisited, 1=in-progress, 2=done. If you hit a 1, there's a cycle.
- Time
- O(V + E)
- Space
- O(V + E)
function canFinishDFS(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
for (const [a, b] of prerequisites) graph[b].push(a);
const color = new Array(numCourses).fill(0);
function dfs(node) {
if (color[node] === 1) return false;
if (color[node] === 2) return true;
color[node] = 1;
for (const next of graph[node]) {
if (!dfs(next)) return false;
}
color[node] = 2;
return true;
}
for (let i = 0; i < numCourses; i++) {
if (!dfs(i)) return false;
}
return true;
}Tradeoff: Same complexity as Kahn's. Uses recursion — stack can blow up on long chains. DoorDash accepts both; mention which you'd prefer in production (iterative Kahn's).
DoorDash-specific tips
DoorDash interviewers grade on whether you CHOOSE between BFS and DFS for the right reason. State: 'I'll use Kahn's BFS — it's iterative, avoids recursion-stack risk, and naturally extends to Course Schedule II.' That framing earns the checkmark.
Common mistakes
- Mixing up edge direction — prerequisites[i] = [a, b] means b -> a in the dependency graph.
- Forgetting that the graph can be disconnected — must iterate all initial 0-in-degree nodes.
- Two-color DFS (only visited/unvisited) — can't detect cycles correctly; you need the in-progress color.
Follow-up questions
An interviewer at DoorDash may pivot to one of these next:
- Course Schedule II (LC 210) — return the topological order.
- Alien Dictionary (LC 269) — derive a topological order from observed word pairs.
- Minimum Height Trees (LC 310) — repeatedly trim leaves.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is edge direction b -> a?
Because prerequisites[i] = [a, b] reads as 'to take a, take b first.' In the dependency graph, b must come before a, so the edge points b -> a.
What if I forget the three-color DFS?
Kahn's BFS is safer — it's a flat counter without recursion. Default to it under stress.
Free learning resources
Curated free links for this problem.