Skip to main content

22. Course Schedule

mediumAsked at Mercury

Determine if all courses can be finished given a list of prerequisites.

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

Problem

There are numCourses labeled 0..numCourses-1 and a list of prerequisite pairs [a, b] meaning you must finish b before a. Return true if you can finish every course; otherwise the prerequisite graph contains a cycle.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • All pairs distinct

Examples

Example 1

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

Example 2

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

Approaches

1. DFS with 3-color marks

Color nodes white/gray/black; a gray-on-gray hit during DFS is a cycle.

Time
O(V+E)
Space
O(V+E)
// state[v] in {0,1,2}; recurse: if 1 return false; if 0 mark 1, recurse neighbors, mark 2. Any false bubbles up.

Tradeoff:

2. Kahn's BFS topological sort

Compute indegrees, enqueue zero-indegree nodes, peel them off and decrement neighbors; if final processed count matches numCourses, no cycle exists.

Time
O(V+E)
Space
O(V+E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let done = 0;
  while (q.length) {
    const v = q.shift();
    done++;
    for (const n of adj[v]) if (--indeg[n] === 0) q.push(n);
  }
  return done === numCourses;
}

Tradeoff:

Mercury-specific tips

Mercury reuses topo-sort to validate KYC pipelines — beneficial-owner verification depends on entity verification, which depends on document upload; cycle in those deps must block onboarding.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →