Course Schedule asked whether an ordering exists. This asks for the ordering itself — and if you wrote Kahn's algorithm for the first one, the answer is already sitting in a variable you threw away. That is the point of the pairing: the boolean version discards the thing the harder version wants.
The problem
Return any valid order in which all numCourses courses can be taken, or an empty
array if none exists.
2, [[1,0]] -> [0,1]
4, [[1,0],[2,0],[3,1],[3,2]] -> [0,1,2,3] or [0,2,1,3]
both valid: 1 and 2 are independent
2, [[1,0],[0,1]] -> [] a cycle
1, [] -> [0]Any valid order. The second example has two, and both are correct — a topological order is not unique unless the graph is a chain, and expecting one specific answer is the first misreading.
Kahn's algorithm, recording as it goes
Identical to problem 207 with one change: instead of counting how many courses were taken, append each one to a list.
207: taken++ then check taken == numCourses
210: order.add(course) then check order.size() == numCoursesThe list is the count. That is the whole difference, and saying so is a better answer than deriving it again — it shows you recognise that the boolean version was throwing information away.
Why the order is valid: a course only enters the queue when its in-degree reaches zero, meaning every prerequisite has already been emitted. So every course appears after all of its prerequisites, which is the definition.
Java
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> unlocks = new ArrayList<>();
for (int i = 0; i < numCourses; i++) unlocks.add(new ArrayList<>());
int[] inDegree = new int[numCourses];
// [a, b] means b must come first, so the edge points b -> a.
for (int[] pair : prerequisites) {
unlocks.get(pair[1]).add(pair[0]);
inDegree[pair[0]]++;
}
Deque<Integer> ready = new ArrayDeque<>();
for (int course = 0; course < numCourses; course++) {
if (inDegree[course] == 0) ready.add(course);
}
int[] order = new int[numCourses];
int placed = 0;
while (!ready.isEmpty()) {
int course = ready.poll();
order[placed++] = course; // the list IS the count
for (int nextCourse : unlocks.get(course)) {
if (--inDegree[nextCourse] == 0) ready.add(nextCourse);
}
}
// Fewer than numCourses placed means the rest are stuck in a cycle.
return placed == numCourses ? order : new int[0];
}
}Returning new int[0] rather than a partial order matters. On a cyclic graph the array
holds a genuinely valid prefix, which is tempting to return and is not what was asked — the contract
is all-or-nothing.
Writing into a pre-sized array with a placed counter avoids a list-to-array
conversion, and placed doubles as the cycle check. Small, but it is the kind of thing
that makes a solution read as deliberate.
Python
from collections import defaultdict, deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
unlocks = defaultdict(list)
in_degree = [0] * numCourses
for course, prerequisite in prerequisites:
unlocks[prerequisite].append(course)
in_degree[course] += 1
ready = deque(c for c in range(numCourses) if in_degree[c] == 0)
order = []
while ready:
course = ready.popleft()
order.append(course)
for next_course in unlocks[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
ready.append(next_course)
return order if len(order) == numCourses else []The DFS version, and why its order is reversed
The recursive answer produces a topological order too, and the detail worth knowing is that it comes out backwards:
dfs(course):
mark in-progress
for each unlocked course: dfs it
mark done
PUSH course <- after its dependents, so it lands deepest
reverse the pushes at the end -> a valid orderA node is recorded only once everything reachable from it is finished, so the finishing order is reverse-topological. Push onto a stack and pop, or append and reverse.
It also needs the three-state marking from problem 207 — in-progress versus done — because a cycle must be detected before any order is returned. Kahn's gets the cycle check for free from the count, which is one more reason to prefer it here.
Complexity
| Time | Space | |
|---|---|---|
| Kahn or DFS | O(V + E) | O(V + E) |
Every course is dequeued once and every edge relaxed once. The output is O(V), and
the adjacency list dominates the rest.
Choosing among valid orders
Because several orders can be valid, the natural follow-up is to ask for a specific one — usually
the lexicographically smallest. Swap the queue for a min-heap and Kahn's algorithm
produces it, at the cost of O(V log V).
That substitution is worth knowing as a general move: Kahn's algorithm with a priority queue picks the best available task at each step, and it is how "shortest schedule", "cheapest first" and similar variants are handled without changing the algorithm's shape.
The pattern
Topological sort with dependencies is one of the most reusable graph tools there is: build order in a package manager, task scheduling with a critical path, spreadsheet cell recomputation, and course planning. Alien Dictionary (269) is the same algorithm with the hard part moved earlier — deriving the edges from adjacent words before sorting them.
The recognition remains the one from problem 207: "order these things given these dependencies" is always this. What changes is only whether you want the answer, the count, or the best one.
What the interviewer is checking
- That any valid order is acceptable, and that several may exist.
- That it is problem 207 with the count replaced by a list.
- The edge direction —
[a, b]meansb → a. - Returning empty rather than a partial order on a cycle.
- No prerequisites, and disconnected components.
- That the DFS order comes out reversed, and why.
- Bonus: a heap for the lexicographically smallest order.