16. Course Schedule II

mediumAsked at Asana

Return a valid ordering of courses given their prerequisites — the same topological sort that Asana's backend runs when computing a linearized task execution plan for a dependency-heavy project.

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

Problem

There are numCourses courses labeled 0 to numCourses - 1 and an array prerequisites where prerequisites[i] = [ai, bi] means course bi must come before course ai. Return any valid ordering to finish all courses. If impossible, return an empty array.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
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]

Explanation: Course 0 is taken first; then 1 and 2 (either order); then 3.

Example 2

Input

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

Output

[]

Explanation: Cycle detected — impossible ordering.

Approaches

1. DFS post-order

Recursively visit all neighbors before adding the current node. Reverse the post-order list to get topological order.

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

function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);

  const state = new Array(numCourses).fill(0); // 0=new,1=visiting,2=done
  const order = [];

  function dfs(node) {
    if (state[node] === 1) return false; // cycle
    if (state[node] === 2) return true;
    state[node] = 1;
    for (const nb of adj[node]) {
      if (!dfs(nb)) return false;
    }
    state[node] = 2;
    order.push(node);
    return true;
  }

  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return [];
  }
  return order.reverse();
}

Tradeoff:

2. Kahn's BFS (optimal)

Track in-degrees, enqueue zero-in-degree nodes, peel them into the result list. If result length < numCourses there is a cycle.

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

function findOrder(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);
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (const nb of adj[node]) {
      inDegree[nb]--;
      if (inDegree[nb] === 0) queue.push(nb);
    }
  }

  return result.length === numCourses ? result : [];
}

Tradeoff:

Asana-specific tips

Asana's engineers think about topological ordering daily — every 'dependencies view' renders tasks in a topological sequence. Interviewers reward candidates who articulate that both DFS post-order and Kahn's BFS are O(V+E), but BFS is iterative and avoids stack overflow on dense graphs. Naming Kahn's algorithm specifically signals you know graph theory, not just pattern-matching.

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

Practice these live with InterviewChamp.AI →