Skip to main content

210. Course Schedule II

mediumAsked at DoorDash

Given courses with prerequisites, return a valid ordering or an empty array if no ordering exists. DoorDash uses this as the Course Schedule follow-up — same cycle detection but you also output the topological order.

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list Course Schedule II as the typical follow-up to LC 207.
  • Blind (2025-12)— DoorDash backend SDE reports note this as a recurring dependency-order question.

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. 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 <= a_i, b_i < numCourses
  • a_i != b_i
  • All the pairs [a_i, b_i] 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: Another valid ordering is [0,1,2,3].

Example 3

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

Approaches

1. Kahn's algorithm (BFS topological sort)

Compute in-degree. Enqueue all 0-in-degree nodes. Pop one to the result, decrement neighbors' in-degree, enqueue any that hit 0. If the result length == numCourses, return it; else return [].

Time
O(V + E)
Space
O(V + E)
function findOrder(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  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);
  }
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const next of graph[node]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }
  return order.length === numCourses ? order : [];
}

Tradeoff: DoorDash's preferred answer. Iterative; clean extension of LC 207. The order array IS the topological sort.

2. DFS with post-order push

DFS each unvisited node. Detect cycles with three-color states. Push to order during post-order; reverse at the end.

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 color = new Array(numCourses).fill(0);
  const order = [];
  function dfs(node) {
    if (color[node] === 1) return false;
    if (color[node] === 2) return true;
    color[node] = 1;
    for (const next of graph[node]) {
      if (!dfs(next)) return false;
    }
    color[node] = 2;
    order.push(node);
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return [];
  }
  return order.reverse();
}

Tradeoff: Same complexity. Uses recursion. The reverse at the end is the standard topological-sort trick from CLRS.

DoorDash-specific tips

DoorDash interviewers grade specifically on the empty-array-on-cycle check. State 'if I pop fewer than numCourses, there's a cycle and I return [].' That sentence proves you understand the connection between topological sort and cycle detection.

Common mistakes

  • Forgetting to return [] when a cycle exists.
  • Mixing up edge direction (b -> a, not a -> b).
  • Forgetting to reverse in the DFS version — pushes are in post-order so the reverse gives the topological order.

Follow-up questions

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

  • Course Schedule (LC 207) — just yes/no, no ordering needed.
  • Alien Dictionary (LC 269) — derive the topological order from observed word pairs.
  • Parallel Courses (LC 1136) — count the minimum semesters.

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 is Kahn's the recommended version?

Iterative (no stack overflow risk), and the output naturally builds during the BFS — no reverse step. Easier to debug under interview pressure.

What if multiple valid orders exist?

Return any. Kahn's gives one specific order based on queue insertion order; DFS gives a different one. Both are valid.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →