Skip to main content

22. Course Schedule

mediumAsked at Tesla

Detect whether a set of prerequisite dependencies can be completed — Tesla applies cycle detection on directed graphs when validating ECU (Electronic Control Unit) boot-order dependencies so no firmware module tries to initialize before its required services are ready.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. You are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai. Return true if you can finish all courses, false otherwise.

Constraints

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

Examples

Example 1

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

Explanation: Take course 0 first, then course 1.

Example 2

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

Explanation: A circular dependency exists between 0 and 1.

Approaches

1. DFS cycle detection with color states

Three-color DFS (white=unvisited, gray=in-progress, black=done). A gray-to-gray back edge signals 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);

  // 0=unvisited, 1=in-progress, 2=done
  const state = new Array(numCourses).fill(0);

  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;  // already cleared
    state[node] = 1;
    for (const neighbor of graph[node]) {
      if (!dfs(neighbor)) return false;
    }
    state[node] = 2;
    return true;
  }

  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff:

2. Kahn's algorithm (topological sort via in-degree)

Count in-degrees; enqueue nodes with 0 in-degree; process BFS and decrement neighbors. 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 graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDegree[a]++;
  }
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Tesla-specific tips

Tesla engineers deal with firmware dependency graphs daily — a cycle in the ECU boot graph causes a deadlock that hard-bricks a module. Interviewers will ask which approach you prefer and why; know that Kahn's is easier to explain iteratively and naturally yields the topological order as a side-product. The follow-up is almost always LC 210 (return the order itself), so have Kahn's extended to collect the queue output in mind.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →