Skip to main content

207. Course Schedule

mediumAsked at Linear

Detect whether a set of course prerequisites forms a cycle. Linear asks this to test directed-graph cycle detection — can you reach for DFS with three-color marking or Kahn's topological sort, and explain the difference?

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Cited in Linear SWE onsite reports as the canonical graph-round question.
  • r/cscareerquestions (2025-11)— Mentioned in Linear new-grad interview threads as a recurring topological sort problem.

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: Cycle: 0 requires 1 and 1 requires 0.

Approaches

1. DFS with three-color cycle detection

Mark each node: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully explored). A GRAY-to-GRAY edge means a back-edge — 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 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: O(V+E). Compact code, but recursive — may hit call-stack limits on dense graphs. Must call hasCycle for every node, not just node 0.

2. Kahn's BFS topological sort

Track in-degrees. Start with zero-in-degree nodes; process them, decrement neighbors. If all nodes are processed, no cycle exists.

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]) {
      if (--inDeg[v] === 0) q.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative — no recursion depth concern. Extends naturally to Course Schedule II (return the actual order). Linear interviewers often ask for the follow-up in the same session.

Linear-specific tips

Linear interviewers grade this on whether you recognize it as cycle detection in a directed graph. State both approaches before coding: 'DFS with three coloring is compact; Kahn's BFS is iterative and extends to returning the full order.' Pick one based on what the interviewer asks for. Always clarify edge direction — prerequisites[i] = [a, b] means b → a.

Common mistakes

  • Confusing edge direction — prerequisites[i] = [a, b] means b must come before a, so the edge is b → a.
  • Treating as undirected — undirected cycle detection uses union-find, which is wrong for directed graphs.
  • Only calling hasCycle from node 0 — the graph may have disconnected components.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual topological order.
  • Course Schedule III (LC 630) — scheduling with deadlines (different problem class, uses a heap).
  • How would you detect a cycle in an undirected graph? (Answer: union-find or DFS checking back edges differently.)

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 Linear prefer?

Both score equally on correctness. Kahn's is preferred for the follow-up (Course Schedule II) since it directly produces the order. DFS with coloring is more compact for the binary question.

What's the most common bug?

Edge direction confusion. Re-read the problem: 'take b before a' means b → a. Build the adjacency list accordingly.

Why count processed nodes in Kahn's?

If all nodes are processed, no node was stuck waiting for a prerequisite it would never get (which would happen if a cycle blocked in-degree from reaching zero).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →