Course Schedule II medium
Description
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Examples
> Case 1:
numCourses = 2, prerequisites = [[1, 0]]
Output: [0, 1]
> Case 2:
numCourses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 2, 1, 3] (or [0, 1, 2, 3])
> Case 3:
numCourses = 1, prerequisites = []
Output: [0]Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= numCourses × (numCourses - 1)
State design
Identical to Course Schedule, but instead of returning a boolean from the count check, we return the output list itself.
Code
O(V + E) time, O(V + E) space.
Variation — lexicographically smallest order
Swap the FIFO queue for a min-heap:
import heapq
def find_order_lex(num_courses, prerequisites):
adj = [[] for _ in range(num_courses)]
indeg = [0] * num_courses
for a, b in prerequisites:
adj[b].append(a); indeg[a] += 1
heap = [i for i in range(num_courses) if indeg[i] == 0]
heapq.heapify(heap)
out = []
while heap:
u = heapq.heappop(heap); out.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: heapq.heappush(heap, v)
return out if len(out) == num_courses else []O((V + E) log V). Useful when the problem wants a deterministic / canonical order.
Analysis
- Time:
O(V + E). - Space:
O(V + E).
Same skin
- Course Schedule — same algorithm, return a boolean instead of the order.
- Alien Dictionary — build the precedence DAG from a list of words, then run this same Kahn’s.
- Sequence Reconstruction — variant that checks whether the topo order is unique.
- Build a Matrix with Conditions — run this exact algorithm twice (rows + cols).