Smallest Valid Course Order from Prerequisite Pairs, with Cycle Detection
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Courses are numbered `0` to `n - 1`, and some courses must be taken before others. Return an order in which every course can be taken, or an empty list if the prerequisites make that impossible. An empty result therefore also tells you whether all the courses can be finished at all.
### Function Signature
```python
def course_order(n: int, prerequisites: list[list[int]]) -> list[int]:
```
### Rules
- Each pair `[course, before]` in `prerequisites` means that course `before` must be taken before course `course`.
- A valid order lists every course from `0` to `n - 1` exactly once, and every course appears after all of its prerequisites.
- Several valid orders can exist. Return the lexicographically smallest one: compare two orders position by position, and the order with the smaller course number at the first position where they differ is the smaller order.
- If no valid order exists, because the prerequisites contain a cycle, return `[]`.
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(prerequisites) <= 10^5`
- Each pair holds two different course numbers between `0` and `n - 1`, and no pair appears twice.
- A chain of prerequisites can be as long as `n` courses.
### Examples
**Example 1**
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]]
Output: [3, 0, 2, 1]
```
Course 3 comes before courses 0 and 2, and course 2 comes before course 1. The valid orders are `[3, 0, 2, 1]`, `[3, 2, 0, 1]` and `[3, 2, 1, 0]`, and the first is the smallest.
**Example 2**
```text
Input: n = 2, prerequisites = [[0, 1], [1, 0]]
Output: []
```
Each course is a prerequisite of the other, so neither can be taken first.
**Example 3**
```text
Input: n = 3, prerequisites = []
Output: [0, 1, 2]
```
With no prerequisites every order is valid, and the smallest is the sorted one.
Overview: Given numbered courses and prerequisite pairs, return the lexicographically smallest order that takes every course after its prerequisites, or an empty list when a cycle makes that impossible. It tests topological sorting, cycle detection and producing a unique canonical ordering.
Courses are numbered `0` to `n - 1`, and some courses must be taken before others. You are given the number of courses `n` and a list `prerequisites`, where each pair `[course, before]` means that course `before` must be taken before course `course`.
Return an order in which every course can be taken, or an empty list if the prerequisites make that impossible. A valid order lists every course from `0` to `n - 1` exactly once, and every course appears after all of its prerequisites. An empty result therefore also tells you whether all the courses can be finished at all.
Several valid orders can exist. Return the lexicographically smallest one: compare two orders position by position, and the order with the smaller course number at the first position where they differ is the smaller order. If no valid order exists, because the prerequisites contain a cycle, return `[]`.
A pair and its reverse (for example `[0, 1]` and `[1, 0]`) are different pairs, so both may appear; together they form a cycle. Every value fits in a signed 32-bit integer.
**Example 1**
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]]
Output: [3, 0, 2, 1]
```
Course 3 comes before courses 0 and 2, and course 2 comes before course 1. The valid orders are `[3, 0, 2, 1]`, `[3, 2, 0, 1]` and `[3, 2, 1, 0]`, and the first is the smallest.
**Example 2**
```text
Input: n = 2, prerequisites = [[0, 1], [1, 0]]
Output: []
```
Each course is a prerequisite of the other, so neither can be taken first.
**Constraints**
- `1 <= n <= 10^5`
- `0 <= len(prerequisites) <= 10^5`
- Each pair holds two different course numbers between `0` and `n - 1`, and no pair appears twice.
- A chain of prerequisites can be as long as `n` courses.
Constraints
- 1 <= n <= 10^5
- 0 <= len(prerequisites) <= 10^5
- Each pair [course, before] holds two different course numbers between 0 and n - 1, and no pair appears twice.
- A chain of prerequisites can be as long as n courses.
Examples
Input: (1, [])
Expected Output: [0]
Explanation: Minimum valid input: a single course with no prerequisites.
Input: (3, [])
Expected Output: [0, 1, 2]
Explanation: Example 3: with no prerequisites every order is valid and the sorted order is the smallest.
Hints
- A course can be placed only once every one of its prerequisites has already been placed, so it helps to know how many prerequisites each course still has outstanding.
- The lexicographic comparison is decided at the earliest position where two orders differ, so think about how small each position can be given what has already been placed.
- If at some point no remaining course has all of its prerequisites satisfied, no valid order exists.