Skip to main content

207. Course Schedule

mediumAsked at Microsoft

Course Schedule is Microsoft's cycle-detection-on-a-directed-graph staple. The question is 'can you finish all courses' which reduces to 'is the prereq graph a DAG.' Two valid answers — DFS with three-state coloring or Kahn's BFS — both score full marks if you can articulate why.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure/Office org onsite reports list Course Schedule as a recurring 30-minute graph medium.
  • Blind (2025-11)— Microsoft L60/L61 reports cite Course Schedule with the topological-sort follow-up (LC 210).

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.

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Explanation: 0 requires 1 requires 0 — cycle.

Approaches

1. Kahn's BFS topological sort (optimal)

Build adjacency list + in-degree array. Push all zero-in-degree nodes. BFS, decrementing in-degree of neighbors and pushing them when they hit zero. If processed count == numCourses, no cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const inDeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    graph[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) {
    const u = queue.shift();
    processed++;
    for (const v of graph[u]) {
      if (--inDeg[v] === 0) queue.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff: Linear in V+E. Microsoft's preferred answer because Kahn's also gives you the actual topological order for free (LC 210 follow-up). The 'processed count' invariant is the cycle check.

2. DFS with three-state coloring

Color each node white (unvisited), gray (in progress), or black (done). DFS from each white node; hitting a gray node mid-DFS means a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[b].push(a);
  const color = new Array(numCourses).fill(0); // 0 white, 1 gray, 2 black
  function dfs(u) {
    if (color[u] === 1) return false; // cycle
    if (color[u] === 2) return true;
    color[u] = 1;
    for (const v of graph[u]) if (!dfs(v)) return false;
    color[u] = 2;
    return true;
  }
  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: Same complexity. The gray = 'on current DFS stack' invariant is what makes back-edge detection correct. Pure boolean visited[] is NOT enough — it can't distinguish a back edge from a forward/cross edge.

Microsoft-specific tips

Microsoft is grading whether you recognize this as cycle-detection. Say: 'I'll model courses as nodes and prereqs as directed edges. The question is whether this directed graph has a cycle — if no, we can finish; if yes, we cannot.' Then pick Kahn's or DFS and explain the cycle-detection invariant (in-degree drains to zero vs. hitting a gray node).

Common mistakes

  • Using a single boolean visited[] in DFS — can't detect back edges, falsely passes cycles.
  • Forgetting that the graph may be disconnected — loop over every starting node, not just node 0.
  • Confusing the edge direction: prerequisites[a] = [b] means b -> a (take b before a).

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual order (same algorithms, just record the order).
  • Course Schedule IV (LC 1462) — transitive prereq queries.
  • What if some prereqs were optional with min cost?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Kahn's or DFS?

Both are O(V+E). Kahn's is preferred at Microsoft because it iteratively gives the topo order (useful for LC 210). DFS is shorter to write but recursion depth can be an issue with large V.

Why is plain visited[] insufficient in DFS?

Because it can't tell whether an already-visited node is on the current path (cycle) or just done (not a cycle). The three-state coloring distinguishes them.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →