27. Course Schedule

mediumAsked at Apple

Detect circular dependencies in a directed graph — Apple's Xcode build system and Swift Package Manager use topological sort to resolve framework dependency graphs; cycle detection is the first thing that must work correctly before any build starts.

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] indicates 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

Explanation: Take course 0 then course 1

Example 2

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

false

Explanation: Cycle: each requires the other

Approaches

1. DFS cycle detection (coloring)

Color each node white (unvisited), gray (in current path), black (done). A gray node reached again means 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);
  // 0=white, 1=gray, 2=black
  const color = new Array(numCourses).fill(0);
  const dfs = (v) => {
    color[v] = 1;
    for (const nb of adj[v]) {
      if (color[nb] === 1) return false; // cycle
      if (color[nb] === 0 && !dfs(nb)) return false;
    }
    color[v] = 2;
    return true;
  };
  for (let i = 0; i < numCourses; i++) {
    if (color[i] === 0 && !dfs(i)) return false;
  }
  return true;
}

Tradeoff:

2. Kahn's algorithm (BFS topological sort)

Compute in-degrees; enqueue zero-in-degree nodes; process in BFS order. If all nodes processed, no cycle exists.

Time: O(V + E)
Space: O(V + E)

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  const inDegree = new Array(numCourses).fill(0);
  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 nb of adj[node]) {
      inDegree[nb]--;
      if (inDegree[nb] === 0) queue.push(nb);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Apple-specific tips

Apple engineers build and maintain Xcode and Swift Package Manager — dependency cycle detection is not a toy problem for them. Mention Kahn's algorithm by name and explain that it naturally produces the build order (not just a yes/no), which is what SPM actually needs. If asked about the DFS approach, explain the three-color technique clearly — Apple interviewers appreciate rigorous state modeling, which reflects their platform-stability culture. Follow-up: 'Return the actual course order' (LC 210) is a common extension.

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

Practice these live with InterviewChamp.AI →