Skip to main content

210. Course Schedule II

mediumAsked at Amazon

Given courses and prerequisites, return a valid course order or empty if impossible. Amazon asks this to test whether you can extend the cycle-detection from Course Schedule I to producing the topological order via Kahn's BFS.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as the topological-sort round.
  • Blind (2025-10)— Recurring Amazon interview problem.

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • All the pairs [ai, bi] are distinct.

Examples

Example 1

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

Example 2

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

Explanation: [0,2,1,3] is also a valid order.

Example 3

Input
numCourses = 1, prerequisites = []
Output
[0]

Approaches

1. Kahn's BFS topological sort (optimal)

Start with all 0-indegree nodes. Pop, add to order, decrement neighbors' indegrees. If neighbor hits 0, enqueue. If order length < numCourses, return [] (cycle detected).

Time
O(V + E)
Space
O(V + E)
function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    inDeg[a]++;
  }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) q.push(i);
  const order = [];
  while (q.length) {
    const u = q.shift();
    order.push(u);
    for (const v of adj[u]) {
      inDeg[v]--;
      if (inDeg[v] === 0) q.push(v);
    }
  }
  return order.length === numCourses ? order : [];
}

Tradeoff: Linear in graph size. Directly produces the topological order. The cycle check is implicit: if we can't process all nodes, there must be a cycle.

2. DFS postorder (alternative)

DFS with three-color cycle detection. After fully processing a node (BLACK), push it to a result stack. Reverse for topological order.

Time
O(V + E)
Space
O(V + E)
function findOrderDFS(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  const order = [];
  let hasCycle = false;
  function dfs(u) {
    if (color[u] === GRAY) { hasCycle = true; return; }
    if (color[u] === BLACK) return;
    color[u] = GRAY;
    for (const v of adj[u]) { dfs(v); if (hasCycle) return; }
    color[u] = BLACK;
    order.push(u);
  }
  for (let i = 0; i < numCourses; i++) if (color[i] === WHITE) { dfs(i); if (hasCycle) return []; }
  return order.reverse();
}

Tradeoff: Same complexity. Slightly more code but the postorder = topological-order-reversed property is a useful mental model.

Amazon-specific tips

Amazon interviewers prefer Kahn's BFS for Course Schedule II because it directly produces the ordering without a post-processing reverse. State out loud: 'Kahn's processes nodes in topological order by definition — popping 0-indegree nodes mimics finishing prereqs.' Skipping that articulation costs the senior-IC signal.

Common mistakes

  • Returning a partial order instead of [] when a cycle exists.
  • Confusing the edge direction (prereq[a, b] means b -> a, not a -> b).
  • Using DFS without reversing the result.

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • What if there are multiple valid topological orders and we need ALL of them?
  • What if the graph were too large for in-memory adjacency lists?
  • Alien Dictionary (LC 269) — extract ordering from string constraints, then topological sort.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why Kahn's instead of DFS?

Kahn's produces the topological order directly. DFS produces a REVERSED topological order (postorder), requiring an extra reverse step. For this problem, Kahn's is cleaner.

How do you detect cycles in Kahn's?

If you can't drain the queue without processing all nodes, the remaining nodes are in cycles. Check order.length === numCourses at the end.

Practice these live with InterviewChamp.AI

Drill Course Schedule II and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →