Skip to main content

18. Course Schedule

mediumAsked at Intuit

Given a list of courses with prerequisites, determine whether you can complete all courses (i.e., the dependency graph has no cycle). Intuit asks this to test cycle detection and reframes it as 'detect circular dependencies in a tax-form rule tree.'

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit TurboTax onsite — cycle detection framed as 'form-rule dependency validation.'
  • LeetCode Discuss (2025-11)— Intuit SWE II graph round, BFS Kahn's algorithm preferred.

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, b] indicates that you must take course b first if you want to take course a. Return true if you can finish all courses. Otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • All pairs are unique.

Examples

Example 1

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

Explanation: Take course 0, then 1.

Example 2

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

Explanation: Cycle: 0 needs 1, 1 needs 0.

Approaches

1. DFS with three-color marking

Mark nodes white (unvisited), gray (in-progress), black (done). A gray-to-gray edge = back edge = 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 color = new Array(numCourses).fill(0); // 0=white,1=gray,2=black
  function dfs(u) {
    if (color[u] === 1) return false;
    if (color[u] === 2) return true;
    color[u] = 1;
    for (const v of adj[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: Clean recursive cycle detection. Risk: stack overflow on deep chains (mitigate with iterative DFS).

2. Kahn's BFS topological sort (optimal)

Compute in-degrees, enqueue all zero-in-degree nodes, repeatedly remove and decrement neighbors. If the count of removed nodes < numCourses, there's a 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 done = 0;
  while (queue.length) {
    const u = queue.shift();
    done++;
    for (const v of adj[u]) {
      if (--inDeg[v] === 0) queue.push(v);
    }
  }
  return done === numCourses;
}

Tradeoff: Iterative — no recursion-depth risk. Naturally produces a valid topological order if needed (see LC 210).

Intuit-specific tips

Intuit specifically asks this because TurboTax has internal 'form-rule trees' where one form's value depends on another's calculation — a cycle would deadlock the calculation engine. They grade for whether you recognize the cycle-detection framing and pick BFS (iterative, no stack risk) over DFS for production code. Bonus signal: mention that returning the topological order (LC 210) is one extra line.

Common mistakes

  • Direction confusion: prerequisites[i] = [a, b] means 'b before a' — building the wrong edge direction inverts the result.
  • Using DFS without three-color marking and missing cycles in DAG-with-cross-edges.
  • Using array.shift() in JS (O(n) per call) — use a queue head index instead for true O(V+E).

Follow-up questions

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

  • Course Schedule II — return the topological order, not just a boolean (LC 210).
  • Course Schedule III — courses have durations and deadlines (LC 630).
  • Detect cycles in a weighted form-rule graph and report the minimal cycle.

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-color DFS instead of just visited/unvisited?

Two-color marking can't distinguish 'currently being processed' from 'fully done.' The gray state catches back edges (gray-to-gray = cycle); the black state lets us skip already-verified subgraphs.

How does this relate to tax-form rule trees?

Intuit's tax engine evaluates forms with dependencies (Form X needs Schedule Y's total). If a customer's custom rule creates a cycle (Form A references Form B which references Form A), the engine must detect this at validation time, not runtime.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →