Skip to main content

207. Course Schedule

mediumAsked at DRW

DRW uses Course Schedule to probe topological sort and cycle detection — the same logic used in dependency resolution for trading system component startup ordering and in detecting circular position-dependency chains in risk models.

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

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2025-Q4)— DRW SWE candidates report graph cycle-detection problems as a recurring medium-difficulty question in onsite coding rounds.
  • Blind (2025-10)— DRW interview threads note Course Schedule is used to test topological sort, with interviewers asking for both DFS and Kahn's algorithm approaches.

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return true if you can finish all courses, otherwise return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < 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: Cycle: 0 → 1 → 0.

Approaches

1. Kahn's algorithm (BFS topological sort)

Compute in-degrees. Enqueue all zero-in-degree nodes. Process each node, decrement neighbors' in-degrees, and enqueue any that reach zero. 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, head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    processed++;
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff: O(V+E) time and space. Kahn's is preferred at DRW because it is iterative and naturally produces the topological order (Course Schedule II extension) without recursion.

2. DFS cycle detection (three-color marking)

Use three states: unvisited (0), in-progress (1), done (2). DFS each node; if you reach an in-progress node, there is 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=unvisited,1=inProgress,2=done
  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already processed
    state[node] = 1;
    for (const neighbor of adj[node]) {
      if (!dfs(neighbor)) return false;
    }
    state[node] = 2;
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E) but uses the call stack — risk of stack overflow for numCourses = 2000 with deep chains. Present Kahn's first; offer DFS as the recursive alternative.

DRW-specific tips

DRW interviewers ask: 'In our trading system, services have startup dependencies — service A cannot start until service B is ready. How do you detect a circular dependency that would deadlock startup?' This is exactly Course Schedule. They then ask for Course Schedule II (return the actual topological order). Always code Kahn's algorithm for DRW — it is iterative and directly produces the order, which is what a real dependency resolver uses.

Common mistakes

  • Confusing the prerequisite edge direction — [a, b] means b → a in the graph (b must come before a).
  • Using DFS without three-color marking — two states (visited/unvisited) cannot distinguish a back edge from a cross edge.
  • Not processing all nodes in Kahn's — if processed < numCourses, the remaining nodes form a cycle.
  • Using recursive DFS without noting call-stack depth risk for large numCourses.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual topological ordering.
  • How would you detect cycles in a trading system's service dependency graph as new services are added incrementally?
  • What is the expected time to find a cycle in a random directed graph with V nodes and E edges?

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?

Every node in a cycle has in-degree > 0 and will never be enqueued. If processed < numCourses after the BFS, the remaining nodes must form one or more cycles.

Why three colors in DFS?

Unvisited (never seen), in-progress (on the current DFS path), and done (fully processed). A back edge — pointing to an in-progress node — indicates a cycle. Two colors cannot distinguish a back edge from a forward or cross edge.

Why does DRW prefer Kahn's?

Kahn's is iterative (no call-stack risk) and naturally emits the topological order as it processes nodes — which is what a service scheduler or build system needs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →