Skip to main content

207. Course Schedule

mediumAsked at DoorDash

Given 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 Alex Chen, 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 <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • All the pairs prerequisites[i] are unique.

Examples

Example 1

Input
numCourses = 2, prerequisites = [[1,0]]
Output
true

Explanation: Take course 0 first then course 1.

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Course Schedule and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →