Course Prerequisite Ordering: Lexicographically Smallest Valid Order or Empty on a Cycle
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
There are `n` courses labelled `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 order satisfies every prerequisite.
The report identifies this coding question only as a medium-difficulty variant of a classic course-ordering problem and does not say what the variant changed. This version fixes one exact set of rules, including a tie rule that makes the answer unique.
### Function Signature
```python
def course_order(n: int, prerequisites: list[list[int]]) -> list[int]:
```
### Rules
- A pair `[a, b]` means course `b` must appear before course `a` in the returned order.
- A valid order lists every course from `0` to `n - 1` exactly once and places every course after all of its prerequisites.
- When several valid orders exist, 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 smaller.
- If no valid order exists because the prerequisites form a cycle, return `[]`.
- A pair may appear more than once; repeated pairs mean the same as a single copy.
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(prerequisites) <= 2 * 10^5`
- `0 <= a <= n - 1`, `0 <= b <= n - 1` and `a != b` for every pair
### Examples
**Example 1**
```text
Input: n = 5, prerequisites = [[0, 3], [2, 3], [2, 4], [1, 0]]
Output: [3, 0, 1, 4, 2]
```
Every valid order places 3 before 0 and 2, places 4 before 2, and places 0 before 1. Other valid orders exist, such as `[3, 4, 0, 1, 2]` and `[4, 3, 2, 0, 1]`, but `[3, 0, 1, 4, 2]` is the lexicographically smallest.
**Example 2**
```text
Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]
Output: []
```
Course 1 must precede 0, course 2 must precede 1, and course 0 must precede 2, which is a cycle.
**Example 3**
```text
Input: n = 3, prerequisites = [[0, 2], [0, 2]]
Output: [1, 2, 0]
```
The repeated pair only requires 2 before 0. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the first is the smallest.
Overview: A graph coding question on prerequisite ordering: given n courses and pairs stating which course must come before another, return the lexicographically smallest order that satisfies every prerequisite, or an empty list when a cycle makes any order impossible. It tests dependency graphs, cycle detection and deterministic tie-breaking.
Read the full ByteDance Software Engineer interview experience this question came from
There are `n` courses labelled `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 order satisfies every prerequisite.
Implement `course_order(n, prerequisites)` under these rules:
- A pair `[a, b]` means course `b` must appear before course `a` in the returned order.
- A valid order lists every course from `0` to `n - 1` exactly once and places every course after all of its prerequisites.
- When several valid orders exist, 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 smaller.
- If no valid order exists because the prerequisites form a cycle, return `[]`.
- A pair may appear more than once; repeated pairs mean the same as a single copy.
**Constraints**
- `1 <= n <= 10^5`
- `0 <= len(prerequisites) <= 2 * 10^5`
- `0 <= a <= n - 1`, `0 <= b <= n - 1` and `a != b` for every pair
- Every value fits in a 32-bit signed integer; no value exceeds 2^31 - 1.
**Example 1**
```text
Input: n = 5, prerequisites = [[0, 3], [2, 3], [2, 4], [1, 0]]
Output: [3, 0, 1, 4, 2]
```
Every valid order places 3 before 0 and 2, places 4 before 2, and places 0 before 1. Other valid orders exist, such as `[3, 4, 0, 1, 2]` and `[4, 3, 2, 0, 1]`, but `[3, 0, 1, 4, 2]` is the lexicographically smallest.
**Example 2**
```text
Input: n = 3, prerequisites = [[0, 2], [0, 2]]
Output: [1, 2, 0]
```
The repeated pair only requires 2 before 0. The valid orders are `[1, 2, 0]`, `[2, 0, 1]` and `[2, 1, 0]`, and the first is the smallest.
Constraints
- 1 <= n <= 10^5
- 0 <= len(prerequisites) <= 2 * 10^5
- 0 <= a <= n - 1, 0 <= b <= n - 1 and a != b for every pair [a, b]
- A pair may appear more than once; a repeated pair means the same as a single copy
Examples
Input: (1, [])
Expected Output: [0]
Explanation: Minimum valid: one course and no prerequisites.
Input: (4, [])
Expected Output: [0, 1, 2, 3]
Explanation: No prerequisites: every course is free, so the smallest order is the identity order.
Hints
- A course can be taken only after every course it depends on is already in the order; a repeated pair adds no extra requirement.
- Orders are compared from the first position, so the choice made at an earlier position outweighs every later one: think about which courses are allowed to sit at the current position.
- If at some point every remaining course still waits on another remaining course, no valid order exists.