207. Course Schedule

Q: Why does Kahn's algorithm detect cycles without explicit marking?

Nodes in a cycle always have in-degree > 0 after all their cycle neighbors are processed. They never enter the queue and are never counted as processed, so the final count falls short of numCourses.

mediumAsked at Glean

Glean tests cycle detection in directed graphs here — the same topological ordering problem that arises in dependency resolution when indexing hierarchically structured enterprise knowledge bases.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

Glassdoor (2025-12)— Glean SWE onsite reports list Course Schedule as a medium-difficulty graph problem that tests topological sort understanding.
Blind (2025-09)— Glean threads mention cycle-detection problems as a recurring theme in their graph-heavy interview set.

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses. Otherwise, return false.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

Examples

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Output

true

Explanation: Take course 0 first, then course 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 (3-color)

Use a visited-state array with three states: 0 = unvisited, 1 = in current DFS path (gray), 2 = fully processed (black). If you encounter a gray node during DFS, a cycle exists.

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=unseen,1=visiting,2=done
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge = cycle
    if (state[node] === 2) return false; // already processed
    state[node] = 1;
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E) time and space. The 3-color approach is clean and handles disconnected graphs via the outer loop. This is the canonical DFS answer.

2. BFS topological sort (Kahn's algorithm)

Compute in-degrees. Add all zero-in-degree nodes to a queue. Process each node, reduce neighbors' in-degrees, and enqueue newly zero-in-degree nodes. If the processed count equals numCourses, no cycle exists.

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

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); inDegree[a]++; }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDegree[i] === 0) queue.push(i);
  let processed = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: Also O(V+E). Iterative — avoids call stack overflow on large graphs. The count check at the end is elegant: if any node is in a cycle, its in-degree never reaches 0 and it is never processed.

Glean-specific tips

Name your approach upfront: 'This is a cycle-detection problem on a directed graph — I can use either DFS with 3-color marking or BFS topological sort (Kahn's algorithm).' Glean engineers love when you know algorithm names. For the follow-up (return the actual order — LC 210), Kahn's algorithm gives you the order for free. Mention that dependency resolution in package managers or build systems uses exactly this algorithm.

Common mistakes

Using only 2 states (visited/unvisited) — you can't distinguish a back edge (cycle) from a cross edge. Three states are essential.
Not running the outer loop for all nodes — the graph may be disconnected; DFS from one node won't reach all components.
Reversing the edge direction when building the adjacency list — prerequisites[i] = [a, b] means b → a (take b before a), not a → b.
Returning the wrong count comparison in Kahn's — processed should equal numCourses, not prerequisites.length.

Follow-up questions

An interviewer at Glean may pivot to one of these next:

Course Schedule II (LC 210) — return a valid ordering of courses, not just true/false.
Alien Dictionary (LC 269) — derive topological order from sorted word lists.
How does this change if you want to find the shortest prerequisite chain for a target course?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Kahn's algorithm detect cycles without explicit marking?

Nodes in a cycle always have in-degree > 0 after all their cycle neighbors are processed. They never enter the queue and are never counted as processed, so the final count falls short of numCourses.

Which approach should I prefer in an interview?

DFS is slightly faster to code and explain. Kahn's is better for follow-ups that require the actual topological order. Present DFS first, mention Kahn's as an alternative.

Practice these live with InterviewChamp.AI

Drill Course Schedule and other Glean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →