Skip to main content

72. Course Schedule II

mediumAsked at Reddit

Return any valid course order given prerequisites. Reddit uses this topo-sort problem to validate dependency-graph linearization — the same shape used when scheduling a chain of database migrations.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site graph 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]

Example 3

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

Approaches

1. DFS post-order

DFS each unvisited node; on completion, prepend to result.

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

Tradeoff: DFS post-order gives reverse-topological. Reverse at the end.

2. Kahn's algorithm (optimal)

BFS from 0-in-degree nodes; append each popped node to result.

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 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 adj[u]) if (--inDeg[v] === 0) queue.push(v);
  }
  return order.length === numCourses ? order : [];
}

Tradeoff: Iterative. The output is the topological order directly — no reverse needed.

Reddit-specific tips

Reddit interviewers expect Kahn's. Bonus signal: explain that any valid topological order is acceptable. Demonstrate cycle detection by returning [] when length < numCourses.

Common mistakes

  • Forgetting the cycle check (order.length === n).
  • Forgetting to reverse the DFS post-order result.
  • Building adjacency in the wrong direction.

Follow-up questions

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

  • Course Schedule (LC 207) — feasibility only.
  • Alien dictionary (LC 269).
  • Sequence reconstruction (LC 444).

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 does the order start from 0-in-degree nodes?

Those have no unmet prerequisites — they can be taken immediately.

What if multiple orderings are valid?

Return any; the problem says any valid answer is acceptable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →