Approach Summary
Kahn's algorithm: start with 0-in-degree nodes. Return ordering; if not all nodes processed, cycle exists.
Full Solution & Approach
This asks for an actual valid order, so run Kahn's algorithm and collect the order instead of just counting. Build the adjacency list and indegree array; seed a queue with all zero-indegree courses. Repeatedly pop a course, append it to the result, and decrement the indegree of every course that depends on it, enqueueing any that reach zero. If the result contains all numCourses courses, return it — it is a valid topological order. If not, a cycle blocks the remaining courses and the answer is an empty array. The BFS-based Kahn's approach is preferred over the DFS three-color variant here because it directly produces the order in the same pass and is easier to reason about under interview time pressure.
Every edge is relaxed once — O(V + E) time. The adjacency list, indegree array, queue, and result use O(V + E) space.
Solution Code
Solution
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = [c for c in range(num_courses) if indegree[c] == 0]
order = []
for c in queue:
order.append(c)
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else []function findOrder(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
indegree[course]++;
}
const queue = [];
for (let c = 0; c < numCourses; c++) {
if (indegree[c] === 0) queue.push(c);
}
const order = [];
for (let i = 0; i < queue.length; i++) {
const c = queue[i];
order.push(c);
for (const nxt of graph[c]) {
if (--indegree[nxt] === 0) queue.push(nxt);
}
}
return order.length === numCourses ? order : [];
}public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
for (int[] p : prerequisites) {
graph.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) queue.offer(c);
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int c = queue.poll();
order[idx++] = c;
for (int next : graph.get(c)) {
if (--indegree[next] == 0) queue.offer(next);
}
}
return idx == numCourses ? order : new int[0];
}vector<int> findOrder(int numCourses, const vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto& p : prerequisites) {
graph[p[1]].push_back(p[0]);
indegree[p[0]]++;
}
queue<int> q;
for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) q.push(c);
vector<int> order;
while (!q.empty()) {
int c = q.front(); q.pop();
order.push_back(c);
for (int next : graph[c]) {
if (--indegree[next] == 0) q.push(next);
}
}
return order.size() == (size_t)numCourses ? order : vector<int>();
}Edge Cases to Watch
- No prerequisites — any order is valid; the queue starts with all courses
- A cycle — return []
- Unreachable courses (no prerequisites and none depending on them) — they simply start in the queue
- A single course — [0]
How to Recognize This Pattern
- Return topological order of courses
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V + E)