Skip to main content

11. Course Schedule

mediumAsked at Confluent

Decide if all courses can be finished given prerequisite edges — Confluent uses it because cycle detection in a DAG maps directly onto detecting circular dependencies in Kafka Connect pipelines.

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

Problem

There are numCourses labeled 0..n-1. prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses, i.e. the prerequisite graph has no cycle.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • All pairs of prerequisites are unique

Examples

Example 1

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

Example 2

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

Approaches

1. DFS cycle detect

Color nodes white/gray/black; if DFS sees a gray neighbor a cycle exists.

Time
O(V+E)
Space
O(V+E)
// color = [0..n-1]; dfs(u): color[u]=1; for v in adj[u]: if color[v]===1 return false; color[u]=2

Tradeoff:

2. Kahn's topological sort

Build indegrees and an adjacency list, push zero-indegree nodes onto a queue, and pop them while decrementing neighbors. If processed count equals numCourses there's 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 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 === n;
}

Tradeoff:

Confluent-specific tips

Confluent loves when you connect topological sort to Connect-pipeline DAGs — call out that partition assignment plus exactly-once semantics demands the pipeline graph itself be acyclic.

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

Practice these live with InterviewChamp.AI →