Skip to main content

210. Course Schedule II

mediumAsked at Uber

Same as Course Schedule but return one valid order to take all courses, or an empty array if impossible. Uber asks this to test topological sort fluency — return the order itself, not just the boolean.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4/L5 onsite reports include this as a recurring graph medium.
  • Blind (2025-12)— Recurring in Uber dispatch / matching team interviews.

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,2,1,3]

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

Example 3

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

Approaches

1. Kahn's BFS topological sort (optimal)

Compute in-degrees. Queue all 0-in-degree nodes. Pop, append to order, decrement neighbors. If you process all nodes, return order; else cycle -> return [].

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

Tradeoff: Iterative, no recursion concerns. Cleanest answer for the order-returning variant.

2. DFS post-order (alternative)

DFS from each unvisited node; push to order on the way out. Reverse the order. Detect cycles with 3-color.

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

Tradeoff: Same complexity, different idiom. Reverse-post-order DFS is the textbook topological sort. Watch the recursion depth on adversarial graphs.

Uber-specific tips

Uber's bar is naming the topological-sort framing before any code: 'Build the prereq -> course graph, find a topological order, return empty if a cycle blocks it.' Kahn's BFS is cleaner to whiteboard than reverse-post-order DFS — but both pass. If you write DFS, mention recursion-stack risk at the 2000-node bound (fine here but worth flagging).

Common mistakes

  • Edge direction reversed (prereq points to course, not course to prereq).
  • DFS without 3-color cycle detection — can return a wrong order when a cycle exists.
  • BFS forgetting to check that the final order length equals numCourses (cycle detection).

Follow-up questions

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

  • Alien Dictionary (LC 269) — topological sort on inferred char ordering.
  • Course Schedule III (LC 630) — scheduling with deadlines, greedy + heap.
  • Parallel Courses (LC 1136) — minimum semesters with topological levels.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Multiple valid orders — does the answer have to be deterministic?

No — the problem says return any valid order. Kahn's BFS gives a deterministic 'smallest-first' order in node-id order, which most graders accept.

DFS or BFS — which is preferred?

Both pass. BFS Kahn is more naturally framed as 'one valid order'. DFS reverse-post-order is the textbook proof. Pick whichever you can write bug-free under pressure.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →