Rank Every Cell of a Distinct-Value Matrix Consistently Within Its Row and Column
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `m x n` matrix of distinct integers. Return a matrix of the same shape in which every value is replaced by its rank, defined by these rules:
- A rank is an integer starting from `1`.
- For two cells in the same row or the same column, the cell with the larger value has a strictly larger rank.
- Ranks are as small as possible under these rules.
Because all values are distinct, the answer is unique. A matrix with one row is the one-dimensional version of the problem.
### Function Signature
```python
def matrix_ranks(matrix: list[list[int]]) -> list[list[int]]:
```
### Rules
- Only cells that share a row or a column constrain each other. Cells in different rows and columns may have any relative ranks.
- "As small as possible" means every cell gets the smallest rank consistent with the rules. With distinct values, one assignment achieves this for all cells at once.
### Constraints
- `1 <= m, n <= 500` and `m * n <= 10^5`
- `-10^9 <= matrix[i][j] <= 10^9`, and all values are distinct
### Examples
**Example 1**
```text
Input: matrix = [[10, 40, 20, 30]]
Output: [[1, 4, 2, 3]]
```
**Example 2**
```text
Input: matrix = [
[1, 5],
[4, 2]
]
Output: [
[1, 2],
[2, 1]
]
```
`1` and `2` share no row or column, so both get rank 1. `4` is larger than `2` in its row and `1` in its column, so it gets rank 2. So does `5`.
**Example 3**
```text
Input: matrix = [
[3, 1, 9],
[8, 2, 7],
[4, 6, 5]
]
Output: [
[2, 1, 6],
[6, 2, 5],
[3, 5, 4]
]
```
Overview: Replace every value in a matrix of distinct integers with the smallest rank such that larger values outrank smaller ones within each row and column. Tests processing values in sorted order, tracking per-row and per-column state, and the one-dimensional special case.