207. Course Schedule

mediumAsked at IBM

Course Schedule is IBM's cycle-detection-in-directed-graph screener — directly relevant to dependency-graph problems in IBM Cloud orchestration and DB2 query planning. The interviewer is grading whether you reach for topological sort (Kahn's or DFS-coloring), whether you handle disconnected nodes, and whether you finish in O(V+E).

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

Glassdoor (2026-Q1)— IBM Cloud-engineering and SWE-3 onsite recurring problem (dependency-graph track).
LeetCode (2026-Q1)— Top-20 IBM-tagged problem (medium tier).
GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive (topological-sort variants).

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

Example 2

Input

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

Output

false

Explanation: Cycle: 0 needs 1 and 1 needs 0.

Approaches

1. Kahn's algorithm — BFS topological sort (optimal)

Build in-degree per node. Queue all in-degree-0 nodes. Pop, decrement neighbor in-degrees, enqueue zeroes. If processed count = numCourses, no cycle.

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 > 0) {
    const node = queue.shift();
    processed++;
    for (const next of adj[node]) {
      inDeg[next]--;
      if (inDeg[next] === 0) queue.push(next);
    }
  }
  return processed === numCourses;
}

Tradeoff: The canonical answer. The 'processed === numCourses' check at the end is what tells you a cycle exists (some nodes were never enqueued because their in-degree never hit 0). Handles disconnected nodes automatically because we seed every in-degree-0 node.

2. DFS with three-color marking

Mark each node WHITE (unvisited), GRAY (in current path), BLACK (done). A GRAY-on-GRAY edge means cycle.

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

function canFinishDFS(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const WHITE = 0;
  const GRAY = 1;
  const BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  const hasCycle = (node) => {
    color[node] = GRAY;
    for (const next of adj[node]) {
      if (color[next] === GRAY) return true;
      if (color[next] === WHITE && hasCycle(next)) return true;
    }
    color[node] = BLACK;
    return false;
  };
  for (let i = 0; i < numCourses; i++) {
    if (color[i] === WHITE && hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: Same O(V+E) but uses recursion stack instead of an explicit queue. Cleaner to write but risks stack overflow on graphs where the longest dependency chain exceeds the recursion-stack limit. State this risk when picking DFS.

IBM-specific tips

IBM Cloud and DB2 interviewers grade cycle-detection problems on whether you mention BOTH Kahn's and DFS-coloring. Pick one for the final code, but state the other as the alternative — they want to confirm you understand both topological-sort frameworks. Kahn's is the IBM-preferred default because it's iterative (no stack risk) and the 'processed count' is an explicit cycle-detector.

Common mistakes

Building edges in the wrong direction — for [a, b] meaning 'a depends on b', the edge is b -> a (b must come first).
Forgetting to seed all in-degree-0 nodes initially — misses disconnected components.
Using a boolean visited array (two states) instead of three colors in the DFS variant — can't distinguish 'in this path' from 'done.'
Comparing processed > 0 instead of processed === numCourses — wrong: cycles still let some nodes process.
Using Array.shift() on a large queue — O(n) per shift; switch to head-index for true O(1).

Follow-up questions

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

Course Schedule II — return the topological order, not just feasibility (LeetCode 210).
What if the graph is too large to fit in memory? (Streaming Kahn's with disk-backed queues — relevant to IBM Cloud orchestration.)
Detect cycles in an UNDIRECTED graph — different algorithm (DFS with parent check).
Find ALL cycles in a directed graph (Johnson's algorithm).

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 for DFS?

Two colors (visited / unvisited) can't tell you whether a neighbor is on the CURRENT recursion path (back edge = cycle) or just finished from a previous DFS root (cross edge, no cycle). The GRAY/BLACK distinction is the cycle-vs-cross-edge marker.

Why does IBM care about this problem?

Dependency graphs are everywhere in IBM products: build systems (Make, Bazel), package managers (yum, apt), microservice startup sequences in OpenShift, query plan validation in DB2. The Course Schedule problem is the cleanest expression of 'can we execute all tasks given the dependency constraints?'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →