Skip to main content

207. Course Schedule

mediumAsked at Gusto

Determine whether all courses can be finished given prerequisite constraints — which is a cycle detection problem on a directed graph. Gusto asks this to test topological sort and graph reasoning in a domain they understand well: dependency graphs in their payroll and benefits configuration.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-12)— Cited in Gusto SWE onsite reports as a graph medium that tests cycle detection and topological ordering.
  • Blind (2025-09)— Gusto threads list Course Schedule as a medium-hard problem that surfaces in senior engineering rounds.

Problem

There are numCourses courses labeled 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. Return false if it is impossible (i.e., there is a cycle).

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

Explanation: Take course 0 then course 1 — no cycle.

Example 2

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

Explanation: Course 0 requires 1 and course 1 requires 0 — a cycle, impossible.

Approaches

1. DFS cycle detection (3-colour marking)

Build adjacency list. DFS from each unvisited node. Mark nodes as 'in-progress' (grey) while exploring and 'done' (black) when finished. A back edge to a grey node means a cycle.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) adj[prereq].push(course);
  // 0 = unvisited, 1 = in-progress, 2 = done
  const state = new Array(numCourses).fill(0);
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge → cycle
    if (state[node] === 2) return false; // already fully explored
    state[node] = 1; // mark in-progress
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2; // mark done
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E) time and space. The 3-colour (unvisited/in-progress/done) pattern is the canonical DFS cycle-detection approach. Explicit and easy to reason about.

2. Topological sort via Kahn's algorithm (BFS)

Compute in-degrees. Start with all zero-in-degree nodes. Remove them, decrement neighbours. If all nodes are processed, no cycle exists.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course);
    inDegree[course]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  let processedCount = 0;
  while (queue.length) {
    const node = queue.shift();
    processedCount++;
    for (const neighbor of adj[node]) {
      if (--inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processedCount === numCourses;
}

Tradeoff: Also O(V+E). Iterative — no recursion stack overhead. Returns true iff all courses are processed, which is equivalent to the graph being acyclic. Preferred when recursion depth could be an issue.

Gusto-specific tips

Frame it as graph problems first: 'This is cycle detection on a directed graph. If there's a cycle, it's impossible to complete all courses.' Gusto interviewers like candidates who name both approaches (DFS 3-colour and Kahn's BFS) and explain the tradeoffs before choosing one. If they ask about the follow-up Course Schedule II (return the ordering), note that Kahn's naturally gives the topological order.

Common mistakes

  • Using a single boolean visited array instead of 3 states — can't distinguish 'currently on the stack' from 'fully processed', causing false negatives.
  • Building the adjacency list in the wrong direction — if [a,b] means 'b is prerequisite of a', then the edge goes from b to a.
  • In Kahn's algorithm, not checking processedCount === numCourses — the algorithm must process all nodes to confirm no cycle.
  • Forgetting to initialise the queue with all zero-in-degree nodes (not just node 0).

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual course ordering or an empty array if impossible.
  • How would you find and report all courses in a cycle?
  • Extend to weighted prerequisites: what if some prerequisites have a required completion order within a time window?

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 do we need 3 states instead of 2?

2 states (visited/unvisited) can't distinguish a cycle from a DAG. A node 'in-progress' (on the current DFS stack) vs 'done' (fully explored) is the key distinction — only a back edge to an in-progress node means a cycle.

What does processedCount < numCourses mean in Kahn's algorithm?

Some nodes had non-zero in-degree throughout — their prerequisites formed a cycle, so they were never enqueued. A cycle prevents complete processing.

Can this problem have multiple valid answers?

The question only asks true/false. For Course Schedule II, multiple topological orderings may exist — the BFS or DFS approach can return any valid one.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →