#210
Course Schedule II
Medium Topological sort (Kahn)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Same prerequisites as Course Schedule. Return any valid order to take all courses, or an empty array if impossible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: give a valid order to take all courses.
Why this works: the order in which Kahn's algorithm removes courses is a topological order.
Example: 4 courses, 1 and 2 need 0, 3 needs 1 and 2
take 0 → then 1, 2 → then 3 → [0, 1, 2, 3]✦Hints open one at a time
Kahn's algorithm produces a topological order as it goes.
If the order has fewer than n courses, there's a cycle.
↗Approach
Same as Course Schedule, but write each polled course into the result array.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
indeg[p[0]]++;
}
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
int[] order = new int[numCourses];
int k = 0;
while (!q.isEmpty()) {
int u = q.poll();
order[k++] = u;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
}
return k == numCourses ? order : new int[0];
}
}!Common mistake
Returning a partial order when a cycle exists — return an empty array instead.
Complexity
- Time: O(V + E).
- Space: O(V + E).
Topic: Graphs
🎬 Episodes 74–85: video coming soon