Skip to main content

207. Course Schedule

mediumAsked at Anduril

Determine whether all courses can be completed given their prerequisites — in other words, detect whether a directed graph contains a cycle. Anduril tests this because dependency cycle detection is fundamental to build system safety, firmware task scheduling, and verifying that mission plans are acyclic before execution.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-12)— Anduril SWE onsite reports cite topological sort and cycle detection as recurring themes.
  • Blind (2025-10)— Anduril candidates describe graph cycle-detection problems as common in systems and embedded roles.

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 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 — a cycle exists.

Approaches

1. DFS cycle detection (3-color marking)

Assign each node a state: unvisited (0), in current path (1), done (2). A cycle exists if DFS reaches a node in state 1 (currently on the path).

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);
  // 0=unvisited, 1=in-progress, 2=done
  const state = new Array(numCourses).fill(0);
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge = cycle
    if (state[node] === 2) return false; // already verified safe
    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). The 3-color pattern (white/gray/black in classic graph theory) is the canonical cycle-detection algorithm. Anduril engineers appreciate when you name it.

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Iteratively remove zero-in-degree nodes and their outgoing edges. If all nodes are removed, no cycle. If nodes remain, a 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) {
    const node = queue.shift();
    processed++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E). Iterative and avoids call-stack depth. Better for embedded contexts where recursion depth is bounded. Kahn's also naturally produces a topological order if needed.

Anduril-specific tips

Name both approaches and state the tradeoff: 'DFS with 3-color marking is intuitive for cycle detection; Kahn's BFS is iterative and avoids stack-overflow risk on deep dependency graphs.' Anduril will often ask for the actual topological ordering as a follow-up (LC 210) — Kahn's gives it naturally. Connect to real systems: dependency resolution in firmware build systems and mission plan validation are direct applications.

Common mistakes

  • Using a simple boolean visited array instead of 3-state marking — a two-state approach can't distinguish an already-completed node from a node currently on the DFS path.
  • Building the adjacency list in the wrong direction — prerequisites[i] = [a,b] means b → a (b must come first).
  • In Kahn's, not starting the queue with all zero-in-degree nodes — nodes with no prerequisites can be taken first.
  • Confusing the check: processed === numCourses means NO cycle; processed < numCourses means cycle detected.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the topological ordering, not just whether it exists.
  • How would you detect cycles in a graph with weighted edges (for priority scheduling)?
  • How would you parallelize Kahn's algorithm to process independent nodes concurrently?

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 3 colors instead of 2 (visited/unvisited)?

With 2 states you can't tell whether a node was reached via the current DFS path (indicating a cycle) or via a previous completed DFS path (safe). The 'in-progress' state captures the difference.

Which approach should I present first at Anduril?

Either is fine. DFS is more naturally recursive; Kahn's is iterative and aligns with Anduril's preference for stack-safe code. Mention both.

What if prerequisites is empty?

All nodes have in-degree 0; Kahn's processes them all in the first batch; processed == numCourses; returns true. DFS visits each node cleanly and returns true.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →