Lexicographically Smallest Course Order From Prerequisite Pairs

There are n courses labeled 0 to n - 1. Each pair [a, b] in prerequisites means that course b must be taken before course a. Return an order in which all n courses can be taken, or an empty list if no such order exists.

Several orders can be valid. Return the lexicographically smallest one: compare two orders position by position, and at the first position where they differ, the order with the smaller course label there is the smaller order.

Function Signature

def course_order(n: int, prerequisites: list[list[int]]) -> list[int]:

Rules

• A valid order contains every course from 0 to n - 1 exactly once, and for every pair [a, b], course b appears before course a.
• If no valid order exists (some courses depend on each other in a cycle), return [].
• Among all valid orders, return the lexicographically smallest.

Constraints

• 1 <= n <= 100000
• 0 <= len(prerequisites) <= 200000
• Each pair [a, b] has 0 <= a < n, 0 <= b < n and a != b.
• No pair appears more than once.

Examples

Example 1

Input:  n = 5, prerequisites = [[2, 4], [0, 4], [1, 0], [3, 1], [3, 2]]
Output: [4, 0, 1, 2, 3]

Every other course depends on course 4, directly or indirectly, so it must come first. Course 3 needs courses 1 and 2, and course 1 needs course 0, so course 3 must come last. The valid orders are [4, 0, 1, 2, 3], [4, 0, 2, 1, 3] and [4, 2, 0, 1, 3], and the first of them is the smallest.

Example 2

Input:  n = 3, prerequisites = [[0, 1], [1, 2], [2, 1]]
Output: []

Courses 1 and 2 each require the other first, so no valid order exists.

Example 3

Input:  n = 3, prerequisites = []
Output: [0, 1, 2]

Lexicographically Smallest Course Order

Hints

1. Which courses could legally be taken first? Only those with no unmet prerequisites.
2. To make the order as small as possible, decide what the best first course is, then ask whether that choice can ever stop you from finishing the remaining courses.
3. If courses remain but none of them has all its prerequisites taken, the remaining courses depend on each other in a cycle.

Approach

Build a directed graph with an edge b -> a for every pair [a, b], and count each course's unmet prerequisites (its in-degree). Keep every course whose prerequisites have all been placed in a min-priority queue keyed by label. Repeatedly remove the smallest available course, append it to the order, and decrement the in-degree of every course that depends on it, adding any course whose in-degree reaches zero.

Invariant: the queue holds exactly the unplaced courses whose prerequisites all appear in the current prefix.

Correctness: if some valid order extends the current prefix, then one also extends it with any available course v first. Take that completion and move v to its front: every prerequisite of v is already in the prefix, and moving v earlier cannot break a rule that requires v before another course. So no choice of an available course can make completion impossible, and the smallest available label is the smallest value any valid order can have at this position. Repeating that choice at every position yields the lexicographically smallest valid order, which is unique.

If the prerequisites contain a cycle, no course on the cycle ever reaches in-degree zero, so fewer than n courses are placed; the function then returns [] instead of the partial order, even when a long valid prefix was built first.

Edge cases: n = 1; no prerequisites (the labels in increasing order); disconnected components, which interleave by label; a single chain that forces an order against label order; and a cycle that appears only after a valid prefix.

• Time complexity: O((n + m) log n), where m = len(prerequisites)
• Space complexity: O(n + m)