Skip to main content

15. Course Schedule

mediumAsked at Baidu

Decide whether all courses can be finished given prerequisite pairs — equivalently, whether a directed graph is acyclic.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. Given a list of prerequisite pairs [a, b] meaning b must be taken before a, return true if all courses can be finished.

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 coloring

Three-color DFS — white/gray/black; encountering a gray node along the DFS path means a cycle.

Time
O(V + E)
Space
O(V + E)
// 0=unvisited, 1=in-progress, 2=done; if dfs hits a 1, return false.
// Equivalent to Kahn but more code paths to bug on a whiteboard.

Tradeoff:

2. Kahn topological sort

Compute in-degrees; queue all zero-in-degree nodes, drain them and decrement neighbors; cycle exists iff fewer than numCourses are drained.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  const indeg = 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 u = q.shift(); done++;
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return done === numCourses;
}

Tradeoff:

Baidu-specific tips

Baidu uses topological sort for query-rewriting pipelines where downstream rules depend on upstream normalizations, so Kahn's BFS is the answer they want plus a sentence on detecting the cycle by the done-count gap.

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

Practice these live with InterviewChamp.AI →