Lexicographically Smallest Course Order From Prerequisite Pairs
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
Input: n = 3, prerequisites = []
Output: [0, 1, 2]
```
Overview: A graph problem that asks for an order in which to take n courses given prerequisite pairs, returning the lexicographically smallest valid order, or an empty list when a cycle makes every order impossible. It tests dependency ordering, cycle detection and a deterministic tie rule.
Read the full ByteDance Software Engineer interview experience this question came from
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.
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 `[]`.
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.
Implement `course_order(n, prerequisites)`, which returns the order as a list of course labels.
### 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.
- Every value fits in a signed 32-bit integer.
### Example 1
```text
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
```text
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.
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
Input: (5, [[2, 4], [0, 4], [1, 0], [3, 1], [3, 2]])
Expected Output: [4, 0, 1, 2, 3]
Explanation: Source example 1: course 4 must come first and course 3 last; [4, 0, 1, 2, 3] is the smallest of the three valid orders.
Input: (3, [[0, 1], [1, 2], [2, 1]])
Expected Output: []
Explanation: Source example 2: courses 1 and 2 require each other, so no valid order exists.
Hints
- Which courses could legally be taken first? Only those with no unmet prerequisites.
- 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.
- If courses remain but none of them has all its prerequisites taken, the remaining courses depend on each other in a cycle.