Skip to main content

207. Course Schedule

mediumAsked at Google

Given courses and prerequisites, return true if all courses can be finished. Google asks this to test whether you reach for cycle detection in a directed graph and can articulate the difference between DFS-with-coloring and Kahn's BFS topological sort.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the graph round.
  • Reddit r/cscareerquestions (2025-10)— Recurring Google new-grad onsite question.

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

Example 2

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

Explanation: There is a cycle: 0 -> 1 -> 0.

Approaches

1. DFS with three-color cycle detection

Color each node WHITE (unvisited), GRAY (in current DFS path), or BLACK (fully explored). A GRAY-to-GRAY edge means a 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, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  function hasCycle(u) {
    if (color[u] === GRAY) return true;
    if (color[u] === BLACK) return false;
    color[u] = GRAY;
    for (const v of adj[u]) if (hasCycle(v)) return true;
    color[u] = BLACK;
    return false;
  }
  for (let i = 0; i < numCourses; i++) if (hasCycle(i)) return false;
  return true;
}

Tradeoff: Linear in graph size. Gray-to-gray edge detection is the canonical cycle-detection trick for directed graphs. Recursion depth = graph depth, watch for stack overflow on huge graphs.

2. Kahn's BFS topological sort (optimal, iterative)

Start with all nodes of in-degree 0; pop, decrement neighbors' in-degrees, enqueue any that hit 0. If we processed all nodes, 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 q = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) q.push(i);
  let processed = 0;
  while (q.length) {
    const u = q.shift();
    processed++;
    for (const v of adj[u]) {
      inDeg[v]--;
      if (inDeg[v] === 0) q.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative (no recursion-depth concern). Naturally extends to LC 210 (Course Schedule II) where you return the actual order — just collect popped nodes into a result array.

Google-specific tips

Google interviewers grade this on whether you recognize it as a cycle-detection problem in a directed graph. Both DFS and BFS solutions are accepted, but Kahn's algorithm is preferred for the follow-up (Course Schedule II) because it directly produces the topological order. State both options out loud, then pick one.

Common mistakes

  • Confusing the edge direction — prerequisites[i] = [a, b] means b must come before a, so the edge goes b -> a.
  • Treating the graph as undirected — cycle-detection in undirected uses union-find, which is wrong here.
  • Forgetting to call hasCycle for every starting node (not just node 0).

Follow-up questions

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

  • Course Schedule II (LC 210): return the actual order.
  • Course Schedule III (LC 630): scheduling with deadlines (different problem class — uses a heap).
  • What if the graph has weighted 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

DFS or BFS — which does Google prefer?

Both score equally on the binary question. Kahn's (BFS) generalizes more cleanly to the 'return the order' follow-up. DFS with coloring is more compact to whiteboard.

What's the most-common bug?

Edge direction confusion. Always re-read the problem to confirm: 'a depends on b' means b -> a in the graph (b enables a).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →