Kth Smallest Element in a Sorted Matrix

Missing Number

Course Schedule II

Return the kth value in an n-by-n matrix whose rows and columns are both sorted ascending.

You are given an `n x n` matrix where every row is sorted in ascending order and every column is also sorted in ascending order.

Return the `k`th smallest element in the matrix. Count duplicates as separate positions in sorted order.

**Input / output**
- Input: `matrix: int[][]`, `k: int`
- Output: the `k`th smallest integer

**Examples**
1. `matrix = [[1,5,9],[10,11,13],[12,13,15]]`, `k = 8` returns `13`.
2. `matrix = [[-5]]`, `k = 1` returns `-5`.
3. `matrix = [[1,2],[1,3]]`, `k = 2` returns `1` because duplicates still occupy separate ranks.

**Constraints**
- `1 <= n <= 300`
- `-10^9 <= matrix[i][j] <= 10^9`
- Each row and each column is sorted ascending.
- `1 <= k <= n * n`

**Edge cases**
- The answer may appear multiple times in the matrix.
- Negative values are allowed.
- `k` can be `1` or `n * n`.

**Target complexity**
- Aim for `O(n log(value range))` time and `O(1)` extra space.

**Hints**
1. Binary-search the answer value, not the index.
2. For a candidate value `mid`, count how many matrix entries are `<= mid` in `O(n)` time by walking from the bottom-left corner.

**Follow-up**
How would the trade-offs change if you used a min-heap that merges rows instead of binary-searching the value range?

- The matrix is not fully flattened in sorted order, but rows and columns still give strong structure.
- That structure is enough to count how many values are below a target without examining every cell from scratch.

Separate matrix order from global order

- Copy every value into one array, sort it, and read the `(k - 1)`th index.
- This is simple and correct, but it spends `O(n^2 log n)` time and `O(n^2)` extra space.

Brute-force by flattening and sorting

- If at least `k` entries are `<= mid`, the true answer is at most `mid`.
- Otherwise, the answer must be larger than `mid`.

Binary-search the answer value

- Start at the bottom-left corner.
- When `matrix[row][col] <= target`, everything above it in that column also qualifies, so add `row + 1` and move right. Otherwise move up.

Count values <= mid in linear matrix time

Trace `matrix = [[1,5,9],[10,11,13],[12,13,15]]`, `k = 8`.

| low | high | mid | count of values <= mid | decision |
|---:|---:|---:|---:|---|
| 1 | 15 | 8 | 2 | need larger values, so `low = 9` |
| 9 | 15 | 12 | 6 | still too few, so `low = 13` |
| 13 | 15 | 14 | 8 | enough values, so `high = 14` |
| 13 | 14 | 13 | 8 | enough values, so `high = 13` |

When `low` meets `high`, that value is the smallest number whose rank is at least `k`.

Dry run / binary-search trace

Binary-search the value range and count rank in `O(n)` per probe, for `O(n log(value range))` time and constant extra space.