Skip to main content

18. Course Schedule

mediumAsked at Chime

Given prerequisite pairs over n courses, determine whether you can finish all courses (i.e., the dependency graph is acyclic).

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

Problem

There are numCourses labeled 0 to numCourses-1, and an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false otherwise.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • All pairs 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 recursion stack

Run DFS from each course; if you re-enter a node still on the current path, there is a cycle.

Time
O(V + E)
Space
O(V + E)
// Build adj[] list
// state[i] in {0 unvisited, 1 visiting, 2 done}
// if dfs returns false (found state===1 again) -> cycle

Tradeoff:

2. Kahn's topological sort BFS

Track in-degrees and repeatedly remove nodes with in-degree zero. If the number of removed nodes equals numCourses there is no cycle.

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

Tradeoff:

Chime-specific tips

Chime uses topological reasoning when scheduling ACH retry steps, so be explicit about the in-degree invariant so the interviewer trusts you understand dependency unlocking.

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 Chime interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →