20. Course Schedule

mediumAsked at Coursera

Detect if a cycle exists in a directed course-prerequisite graph, a topological sort problem with direct real-world relevance to Coursera's own curriculum dependency engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

There are numCourses courses 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 if a cycle exists.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
No duplicate prerequisites

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 color marking (detect cycle)

Color nodes: 0=unvisited, 1=in-stack, 2=done. If DFS hits a node in-stack, a cycle exists.

Time: O(V+E)
Space: O(V+E)

function canFinish(n, prereqs) {
  const adj = Array.from({length:n}, ()=>[]);
  for (const [a,b] of prereqs) adj[b].push(a);
  const color = new Array(n).fill(0);
  function hasCycle(v) {
    color[v] = 1;
    for (const u of adj[v]) {
      if (color[u] === 1) return true;
      if (color[u] === 0 && hasCycle(u)) return true;
    }
    color[v] = 2;
    return false;
  }
  for (let i = 0; i < n; i++) if (color[i] === 0 && hasCycle(i)) return false;
  return true;
}

Tradeoff:

2. Kahn's BFS (topological sort)

Build in-degree counts; enqueue courses with 0 prerequisites; process and decrement neighbors. If all courses are processed, no cycle exists.

Time: O(V+E)
Space: O(V+E)

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

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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

Practice these live with InterviewChamp.AI →