Course Schedule II
Problem
There are a total of n courses you have to take labelled from 0 to n - 1. Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai. Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.
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.
n = 4, prereqs = [[1,0],[2,0],[3,1],[3,2]][0, 1, 2, 3]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>{};
}Explanation
We must output a valid order to take all courses, respecting prerequisites. This is topological sort, and the code uses Kahn's algorithm: repeatedly take any course that currently has no unmet prerequisites.
First we build a directed graph where each prerequisite [a, b] becomes an edge b → a (take b before a), and we track indeg[a], the number of prerequisites still blocking course a. Every course with indeg == 0 can be taken right away, so we seed the queue with those.
Then we loop: pop a course u, append it to order, and for each course v that depended on u, drop indeg[v] by one. If that count reaches zero, v is now unlocked, so we push it onto the queue.
Example: n=4, prereqs=[[1,0],[2,0],[3,1],[3,2]]. Only course 0 starts free. Taking 0 unlocks 1 and 2; taking those unlocks 3. A valid order is [0, 1, 2, 3].
If a cycle exists, some courses never reach indeg 0 and never leave the queue. So if len(order) != n, we return an empty list to signal it is impossible.