Skip to main content

19. Course Schedule

mediumAsked at Quora

Detect a cycle in a directed graph of prerequisites — Quora uses this exact topological-sort check to validate that answer-dependency graphs in their knowledge graph have no circular references.

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

Problem

There are numCourses courses labeled 0 to numCourses - 1. You are given 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 there is a cycle.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a, b < numCourses
  • All prerequisite pairs are distinct

Examples

Example 1

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

Explanation: Take course 0 then 1. No cycle.

Example 2

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

Explanation: Courses 0 and 1 depend on each other — cycle detected.

Approaches

1. DFS cycle detection (coloring)

Mark nodes white/grey/black. A back-edge to a grey (in-progress) node signals a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const state = new Array(numCourses).fill(0); // 0=white,1=grey,2=black
  function hasCycle(node) {
    if (state[node] === 1) return true;
    if (state[node] === 2) return false;
    state[node] = 1;
    for (const nb of adj[node]) {
      if (hasCycle(nb)) return true;
    }
    state[node] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Kahn's BFS (in-degree topological sort)

Compute in-degrees; enqueue zero-in-degree nodes; process and decrement neighbours. If all nodes are processed, 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 queue = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) queue.push(i);
  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const nb of adj[node]) {
      if (--inDeg[nb] === 0) queue.push(nb);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Quora-specific tips

Quora uses Kahn's BFS variant internally because it's iterative and doesn't risk stack overflow on deep graphs. Know both and be ready to discuss which degrades more gracefully when the graph is dense.

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

Practice these live with InterviewChamp.AI →