17. Course Schedule

mediumAsked at CircleCI

Detect if a directed course prerequisite graph has a cycle, directly mirroring CircleCI's cycle detection in pipeline job dependency graphs.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. Given prerequisites[i] = [a, b] meaning you must take course b before course a, return true if you can finish all courses (i.e., the prerequisite graph is a DAG).

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
No self-loops or duplicate edges

Examples

Example 1

Input

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

Output

true

Example 2

Input

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

Output

false

Approaches

1. DFS cycle detection

Use three-color DFS (unvisited, visiting, visited) to detect back edges.

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);
  const state = new Array(numCourses).fill(0);
  function dfs(node) {
    if (state[node] === 1) return false;
    if (state[node] === 2) return true;
    state[node] = 1;
    for (const nb of graph[node]) if (!dfs(nb)) 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 topological sort (BFS)

Compute in-degrees, enqueue zero-in-degree nodes, and process them; if all nodes are processed, there is no cycle. Mirrors how CircleCI schedules pipeline jobs.

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 count = 0;
  while (queue.length) {
    const node = queue.shift();
    count++;
    for (const nb of graph[node]) {
      indegree[nb]--;
      if (indegree[nb] === 0) queue.push(nb);
    }
  }
  return count === numCourses;
}

Tradeoff:

CircleCI-specific tips

CircleCI considers this a core problem — they expect you to name Kahn's algorithm, discuss how it scales to thousands of parallel jobs, and handle disconnected graph components.

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

Practice these live with InterviewChamp.AI →