18. Course Schedule II

mediumAsked at CircleCI

Return a valid topological ordering of courses, which maps directly to CircleCI's job execution order in a pipeline DAG.

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

Problem

Given numCourses and a list of prerequisites, return the ordering of courses to finish all of them. If it is impossible (cycle exists), return an empty array.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
All prerequisite pairs are distinct

Examples

Example 1

Input

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

Output

[0,1,2,3]

Example 2

Input

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

Output

[0,1]

Approaches

1. DFS post-order

Run DFS and push each node to result after all neighbors are processed; reverse at end.

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

function findOrder(n, prereqs) {
  const graph = Array.from({length: n}, () => []);
  for (const [a, b] of prereqs) graph[b].push(a);
  const state = new Array(n).fill(0), order = [];
  function dfs(u) {
    if (state[u] === 1) return false;
    if (state[u] === 2) return true;
    state[u] = 1;
    for (const v of graph[u]) if (!dfs(v)) return false;
    state[u] = 2; order.push(u); return true;
  }
  for (let i = 0; i < n; i++) if (!dfs(i)) return [];
  return order.reverse();
}

Tradeoff:

2. Kahn's BFS topological sort

Process nodes with zero in-degree first, producing a BFS-level topological order that naturally expresses which jobs can run in parallel.

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

function findOrder(n, prereqs) {
  const indegree = new Array(n).fill(0);
  const graph = Array.from({length: n}, () => []);
  for (const [a, b] of prereqs) { graph[b].push(a); indegree[a]++; }
  const queue = [], order = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of graph[u]) { if (--indegree[v] === 0) queue.push(v); }
  }
  return order.length === n ? order : [];
}

Tradeoff:

CircleCI-specific tips

CircleCI prizes the Kahn's approach because it naturally groups jobs by parallelizable wave — describe how nodes processed in the same BFS level can run concurrently on separate workers.

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 II 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 →