23. Course Schedule

mediumAsked at Unity

Detect a cycle in a directed prerequisite graph to decide if all courses can finish — the same dependency-cycle check Unity's Package Manager runs to verify that no two packages create a circular import before loading into the editor.

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] = [a, b] means you must take course b before course a. Return true if you can finish all courses, or false if a cycle makes it impossible.

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 0 first, then 1. No cycle.

Example 2

Input

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

Output

false

Explanation: 0 requires 1, and 1 requires 0 — a cycle.

Approaches

1. DFS cycle detection (three-color)

Color nodes: 0=unvisited, 1=in-progress, 2=done. A back-edge to an in-progress node 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);
  const color = new Array(numCourses).fill(0);
  function dfs(u) {
    if (color[u] === 1) return false; // cycle
    if (color[u] === 2) return true;  // already verified
    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:

2. Topological sort (Kahn's BFS)

Compute in-degrees; enqueue zero-in-degree nodes; repeatedly remove them and reduce neighbor in-degrees. If all nodes are 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 u = queue.shift();
    processed++;
    for (const v of adj[u]) {
      if (--indegree[v] === 0) queue.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff:

Unity-specific tips

Unity interviewers connect this directly to package dependency resolution — name the Kahn's approach as the iterative option that avoids recursion-stack overflow on large dependency graphs (thousands of packages), which is a real constraint the Package Manager team has dealt with.

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

Practice these live with InterviewChamp.AI →