Find a Course Order for All Prerequisites
Problem
Given n courses and a list of prerequisite pairs [a, b] (you must take b before a), return any ordering that satisfies all prerequisites — or an empty list if no ordering exists.
Build the directed graph b → a and run Kahn's algorithm. The order in which courses are dequeued is itself a valid topological order. If fewer than n courses ever leave the queue, a cycle blocked progress and there is no valid order.
Input
n = 4, prereqs = [[1,0],[2,0],[3,1],[3,2]]Output
[0, 1, 2, 3]Course 0 has no prereqs; once finished, 1 and 2 are unlocked; 3 unlocks last.
from collections import deque
def find_order(n, prereqs):
g = [[] for _ in range(n)]
indeg = [0] * n
for a, b in prereqs:
g[b].append(a); indeg[a] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return order if len(order) == n else []function findOrder(n, prereqs) {
const g = Array.from({ length: n }, () => []);
const indeg = new Array(n).fill(0);
for (const [a, b] of prereqs) { g[b].push(a); indeg[a]++; }
const q = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
const order = [];
while (q.length) {
const u = q.shift(); order.push(u);
for (const v of g[u]) if (--indeg[v] === 0) q.push(v);
}
return order.length === n ? order : [];
}class Solution {
public int[] findOrder(int n, int[][] prereqs) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : prereqs) { g.get(e[1]).add(e[0]); indeg[e[0]]++; }
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
int[] order = new int[n]; int k = 0;
while (!q.isEmpty()) {
int u = q.poll(); order[k++] = u;
for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
}
return k == n ? order : new int[0];
}
}vector<int> findOrder(int n, vector<vector<int>>& prereqs) {
vector<vector<int>> g(n);
vector<int> indeg(n, 0);
for (auto& e : prereqs) { g[e[1]].push_back(e[0]); indeg[e[0]]++; }
queue<int> q;
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}
return (int)order.size() == n ? order : vector<int>{};
}