207. Course Schedule

Q: Why three colors instead of two booleans (visited + inStack)?

Three colors are equivalent but express intent more cleanly. Color 2 (black) means 'fully processed — safe to skip.' With two booleans, you need to reset inStack on backtrack, which is easy to forget.

Q: What does Kahn's algorithm fail to do that DFS succeeds at?

Kahn's doesn't naturally identify which nodes form the cycle — it just reports that a cycle exists (processed < numCourses). DFS can be extended to record the cycle path.

Q: Is topological sort uniquely defined?

No — multiple valid topological orderings exist whenever there are nodes with no ordering constraint between them. If you need lexicographically smallest, use a min-heap instead of a plain queue in Kahn's.

mediumAsked at Citadel

Cycle detection in a directed graph is a fundamental primitive in dependency resolution — trade execution sequencing, pipeline DAG validation, and margin calculation dependency graphs all require verifying no circular dependencies exist. Citadel expects both DFS (with coloring) and topological-sort (Kahn's) approaches.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

Glassdoor (2025-12)— Citadel SWE interviewees report graph cycle detection and topological sort as a recurring category in medium-difficulty on-site rounds.
Blind (2025-10)— Citadel SWE threads identify Course Schedule as a benchmark for graph fundamentals — BFS topo-sort vs DFS coloring is a common follow-up.

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 0 first, then 1. No cycle.

Example 2

Input

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

Output

false

Explanation: Circular dependency: 0 requires 1 and 1 requires 0.

Approaches

1. DFS with three-color marking

Color nodes: 0 = unvisited, 1 = in current path (gray), 2 = fully processed (black). A back edge (visiting a gray node) indicates 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 color = new Array(numCourses).fill(0); // 0=unvisited, 1=visiting, 2=done

  function hasCycle(node) {
    if (color[node] === 1) return true;  // back edge -> cycle
    if (color[node] === 2) return false; // already processed, safe
    color[node] = 1; // mark visiting
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    color[node] = 2; // mark done
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E) time and space. Three-color marking is cleaner than a simple visited/inStack boolean pair because it avoids the need to reset inStack after backtracking. This is the DFS-first answer.

2. Kahn's algorithm (BFS topological sort)

Count in-degrees. Start with all nodes of in-degree 0. Process them via BFS, decrementing neighbors' in-degrees. If all nodes are processed, the graph is acyclic.

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, qi = 0;
  while (qi < queue.length) {
    const node = queue[qi++];
    processed++;
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E) time, O(V) queue space. Iterative — no recursion stack depth issue. Also produces the topological order as a side effect. Citadel may prefer this because it's easier to reason about in a distributed execution context.

Citadel-specific tips

State both approaches upfront and ask which one the interviewer prefers. DFS with coloring is compact; Kahn's is iterative and naturally parallelizable (zero in-degree nodes can be processed in parallel). In a trading pipeline dependency graph, Kahn's maps to a task scheduler that can batch-execute all tasks with no outstanding dependencies simultaneously — mention this framing. Also: 'The check processed === numCourses at the end tells us whether all nodes were reachable from the zero-in-degree frontier, i.e., no cycle existed.'

Common mistakes

Using a simple visited boolean instead of three colors in DFS — you can't distinguish back edges (cycle) from cross edges (already processed in another path) with a binary flag alone.
Forgetting to initialize the adjacency list for all nodes — nodes with no edges still exist and must be visited.
In Kahn's, not checking processed === numCourses at the end — just checking queue empty is insufficient (queue empties when stuck in a cycle too).
Building the graph with edge direction reversed — prerequisites[i] = [a, b] means b → a, not a → b. Getting this backward flips the topological order.

Follow-up questions

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

Course Schedule II (LC 210) — return the actual topological order, not just a boolean.
Alien Dictionary (LC 269) — infer topological order from a sorted word list.
How would you detect cycles in an undirected graph?

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 three colors instead of two booleans (visited + inStack)?

Three colors are equivalent but express intent more cleanly. Color 2 (black) means 'fully processed — safe to skip.' With two booleans, you need to reset inStack on backtrack, which is easy to forget.

What does Kahn's algorithm fail to do that DFS succeeds at?

Kahn's doesn't naturally identify which nodes form the cycle — it just reports that a cycle exists (processed < numCourses). DFS can be extended to record the cycle path.

Is topological sort uniquely defined?

No — multiple valid topological orderings exist whenever there are nodes with no ordering constraint between them. If you need lexicographically smallest, use a min-heap instead of a plain queue in Kahn's.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →