Check Whether a Proposed Course Order Respects Every Prerequisite
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. Given a proposed order of courses, decide whether it is a valid order in which to take them all.
### Function Signature
```python
def is_valid_course_order(n: int, prerequisites: list[list[int]], order: list[int]) -> bool:
```
### Rules
- Each pair `[course, before]` in `prerequisites` means that course `before` must be taken before course `course`.
- `order` is valid when it lists every course from `0` to `n - 1` exactly once and, for every pair `[course, before]`, `before` appears earlier in `order` than `course`.
- An order that leaves out a course or lists a course twice is not valid.
- If the prerequisites contain a cycle, no order can be valid, so the answer is `False`.
### 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.
- `0 <= len(order) <= 2 * 10^5`, and every value in `order` is between `0` and `n - 1`.
### Examples
**Example 1**
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]], order = [3, 2, 0, 1]
Output: True
```
Course 3 comes before courses 0 and 2, and course 2 comes before course 1.
**Example 2**
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]], order = [3, 1, 2, 0]
Output: False
```
Course 1 is placed before its prerequisite, course 2.
**Example 3**
```text
Input: n = 3, prerequisites = [[1, 0]], order = [0, 1]
Output: False
```
The order satisfies the only prerequisite but never takes course 2.
Overview: Given courses, prerequisite pairs and a proposed order, decide whether the order lists every course exactly once and places each course after all of its prerequisites. It tests position indexing, permutation checks and careful handling of missing or repeated courses.
Courses are numbered `0` to `n - 1`, and some courses must be taken before others. You are given the number of courses `n`, a list `prerequisites` of pairs, and a proposed order `order`. Decide whether `order` is a valid order in which to take all of the courses: return `True` if it is and `False` otherwise.
### Rules
- Each pair `[course, before]` in `prerequisites` means that course `before` must be taken before course `course`.
- `order` is valid when it lists every course from `0` to `n - 1` exactly once and, for every pair `[course, before]`, `before` appears earlier in `order` than `course`.
- An order that leaves out a course or lists a course twice is not valid. (`order` may therefore be shorter or longer than `n`, and may repeat or omit courses.)
- If the prerequisites contain a cycle, no order can be valid, so the answer is `False`.
### Example 1
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]], order = [3, 2, 0, 1]
Output: True
```
Course 3 comes before courses 0 and 2, course 2 comes before course 1, and every course from 0 to 3 appears exactly once.
### Example 2
```text
Input: n = 4, prerequisites = [[0, 3], [2, 3], [1, 2]], order = [3, 1, 2, 0]
Output: False
```
Course 1 is placed before its prerequisite, course 2.
### 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.
- `0 <= len(order) <= 2 * 10^5`, and every value in `order` is between `0` and `n - 1`.
- Every value fits in a signed 32-bit integer; no input value can exceed 2^31 - 1.
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.
- 0 <= len(order) <= 2 * 10^5, and every value in order is between 0 and n - 1.
- Every value fits in a signed 32-bit integer; no input value can exceed 2^31 - 1.
Examples
Input: (1, [], [0])
Expected Output: True
Explanation: Minimum valid: one course, no prerequisites, and the order lists it exactly once.
Input: (1, [], [])
Expected Output: False
Explanation: Minimum: an empty order omits course 0.
Hints
- Before checking any prerequisite, think about what the length of order and the set of courses it lists must look like for the order to be valid at all.
- Each pair [course, before] only asks where those two courses sit in order relative to each other; think about how to answer that quickly for many pairs.
- Remember that the prerequisites may contain a cycle; make sure your answer is False in that case.