Course Schedule II

Kth Smallest Element in a Sorted Matrix

Maximum Product Subarray

Return a valid topological ordering of courses, or an empty array if a cycle blocks completion.

There are `numCourses` courses labeled from `0` to `numCourses - 1`. Each prerequisite pair `[a, b]` means you must take course `b` before course `a`.

Return one valid ordering of every course. If the prerequisite graph contains a cycle, return `[]`.

**Input / output**
- Input: `numCourses: int`, `prerequisites: int[][]`
- Output: `int[]` containing a valid order, or `[]` if impossible

**Examples**
1. `numCourses = 2`, `prerequisites = [[1, 0]]` returns `[0, 1]`.
2. `numCourses = 4`, `prerequisites = [[1,0],[2,0],[3,1],[1,2]]` returns `[0, 2, 1, 3]`.
3. `numCourses = 2`, `prerequisites = [[1, 0], [0, 1]]` returns `[]` because the cycle makes every order invalid.

**Constraints**
- `1 <= numCourses <= 2000`
- `0 <= prerequisites.length <= 5000`
- `0 <= a, b < numCourses` and `a != b` for every pair `[a, b]`.

**Edge cases**
- Some courses may have no prerequisites at all.
- The graph may contain multiple disconnected components.
- A cycle anywhere in the graph invalidates the entire schedule.

**Target complexity**
- Aim for `O(V + E)` time and `O(V + E)` space.

**Hints**
1. Count how many prerequisites each course still needs.
2. Repeatedly remove any course whose indegree is zero and update its outgoing neighbors.

**Follow-up**
How would you detect the cycle with DFS color states instead of Kahn's breadth-first topological sort?

- Every course is a vertex and every prerequisite pair is a directed edge.
- We need a topological ordering: every prerequisite must appear before the course that depends on it.

Recognize the graph problem

- In each round, search for courses whose prerequisites are already taken.
- This is correct but can revisit the full prerequisite list many times, giving roughly `O(V * E)` work.

Brute-force by repeatedly scanning prerequisites

- Precompute each course's indegree and adjacency list once.
- Then each edge is processed exactly once when its prerequisite is removed from the queue.

Use indegrees to avoid repeated rescans

- Seed the queue with every course whose indegree is zero.
- Pop courses, append them to the answer, and decrement the indegree of their outgoing neighbors.

Run Kahn's algorithm with a FIFO queue

Trace `numCourses = 4`, `prerequisites = [[1,0],[2,0],[3,1],[1,2]]`.

| step | queue before pop | popped | indegree updates | order |
|---|---|---:|---|---|
| start | `[0]` | - | indegrees = `[0,2,1,1]` | `[]` |
| 1 | `[0]` | `0` | `1 -> 1`, `2 -> 0`, enqueue `2` | `[0]` |
| 2 | `[0,2]` | `2` | `1 -> 0`, enqueue `1` | `[0,2]` |
| 3 | `[0,2,1]` | `1` | `3 -> 0`, enqueue `3` | `[0,2,1]` |
| 4 | `[0,2,1,3]` | `3` | none | `[0,2,1,3]` |

Every course appears exactly once, so the graph is acyclic and the built order is valid.

Dry run / queue trace

Kahn's algorithm processes each course and prerequisite edge once, giving `O(V + E)` time with `O(V + E)` graph storage.