26. Course Schedule

mediumAsked at Spotify

Determine whether all courses can be finished given prerequisite pairs — cycle detection in a directed graph, mirroring how Spotify validates dependency ordering in its microservice deployment pipeline.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

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, otherwise return false.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
All prerequisite 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 → 1 → 0.

Approaches

1. DFS cycle detection

Build an adjacency list; for each unvisited node, DFS and track nodes in the current recursion path. If we revisit a path-node, a cycle exists.

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);
  // 0 = unvisited, 1 = in current path, 2 = fully processed
  const state = new Array(numCourses).fill(0);
  const hasCycle = (node) => {
    if (state[node] === 1) return true;
    if (state[node] === 2) return false;
    state[node] = 1;
    for (const nei of adj[node]) {
      if (hasCycle(nei)) return true;
    }
    state[node] = 2;
    return false;
  };
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Topological sort (Kahn's BFS)

Count in-degrees; enqueue zero-in-degree nodes; process each by decrementing neighbor in-degrees. If we process all nodes, 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 [a, b] of prerequisites) {
    adj[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 nei of adj[node]) {
      inDegree[nei]--;
      if (inDegree[nei] === 0) queue.push(nei);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Spotify-specific tips

Spotify's infrastructure teams deal with service dependency graphs daily. Frame your solution around that: 'In a microservice graph, a cycle means two services are waiting on each other — the system deadlocks.' The Kahn's BFS approach tends to resonate more with Spotify engineers because it's how real build-systems (Gradle, Bazel) detect circular dependencies.

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 Spotify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →