Skip to main content

89. Course Schedule

mediumAsked at Vercel

Given a list of course prerequisites, determine if you can finish all courses. Vercel asks this for cycle detection in a directed graph — literally the same algorithm they use to detect dependency cycles in their deployment graph (build A depends on B, B on C, C on A is a deploy-killer).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel build-system onsite; literally their problem.
  • Blind (2026-Q1)— Reported as the canonical Vercel build engineer screen.

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

Example 2

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

Approaches

1. DFS with three-state coloring

Each node: white (unvisited), gray (in current DFS path), black (done). Cycle iff DFS reaches a gray node.

Time
O(V + E)
Space
O(V + E)
function canFinish(n, prereqs) {
  const graph = Array.from({length: n}, () => []);
  for (const [a, b] of prereqs) graph[b].push(a);
  const color = new Array(n).fill(0); // 0=white, 1=gray, 2=black
  function dfs(u) {
    if (color[u] === 1) return false;
    if (color[u] === 2) return true;
    color[u] = 1;
    for (const v of graph[u]) if (!dfs(v)) return false;
    color[u] = 2;
    return true;
  }
  for (let i = 0; i < n; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: Classic cycle detection. The gray state captures 'this node is on the current recursion path' — revisiting it means a cycle.

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Start with all 0-in-degree nodes. Repeatedly dequeue and decrement neighbors' in-degrees. If you process all nodes, no cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(n, prereqs) {
  const graph = Array.from({length: n}, () => []);
  const inDeg = new Array(n).fill(0);
  for (const [a, b] of prereqs) { graph[b].push(a); inDeg[a]++; }
  const queue = [];
  for (let i = 0; i < n; i++) if (inDeg[i] === 0) queue.push(i);
  let processed = 0;
  while (queue.length) {
    const u = queue.shift();
    processed++;
    for (const v of graph[u]) { if (--inDeg[v] === 0) queue.push(v); }
  }
  return processed === n;
}

Tradeoff: Produces a valid topological order as a side effect. Often preferred over DFS coloring because it gives the order for free.

Vercel-specific tips

Vercel grades either approach. Bonus signal: knowing both AND mentioning that Kahn's produces the actual build order while DFS coloring just detects cycles. They may follow up with LC 210 (return the order) — Kahn's is the natural fit there.

Common mistakes

  • Building the graph in the wrong direction (a depends on b means edge b -> a, not a -> b).
  • Confusing gray and black — gray is 'in progress', black is 'done'. Hitting gray = cycle.
  • Off-by-one on in-degree initialization.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Course Schedule II (LC 210) — return the order.
  • Alien Dictionary (LC 269) — topological sort on letters.
  • Detect cycle in a directed graph (LC 207 is the answer).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

DFS coloring vs Kahn's — which to pick?

DFS is recursive, more concise. Kahn's is iterative and gives the build order. For Vercel's deploy-graph context, Kahn's matches the actual task better.

Direction of the edge?

[a, b] = 'to take a, take b first' = b enables a = edge b -> a. Easy to flip; always sanity-check with the smallest example.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →