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.
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.
Only cells that share a row or a column constrain each other; cells in different rows and different columns may have any relative ranks. "As small as possible" means every cell gets the smallest rank consistent with the rules. Because all values are distinct, one assignment achieves this for all cells at once, so the answer is unique. A matrix with one row is the one-dimensional version of the problem.
Implement `matrix_ranks(matrix)`. Return the ranks as a list of `m` rows of `n` integers each, where the entry at row `i`, column `j` is the rank of `matrix[i][j]`.
### Constraints
- `1 <= m, n <= 500` and `m * n <= 10^5`
- `-10^9 <= matrix[i][j] <= 10^9`, and all values are distinct
- Every input value and every rank (at most `m * n`) fits in a signed 32-bit integer; nothing exceeds 2^31 - 1, so Java and C++ use `int`.
### Example 1
```text
Input: matrix = [[10, 40, 20, 30]]
Output: [[1, 4, 2, 3]]
```
With one row, each value's rank is its position in sorted order.
### 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`.
Constraints
- 1 <= m, n <= 500 and m * n <= 10^5
- -10^9 <= matrix[i][j] <= 10^9, and all values are distinct
- matrix is rectangular: every row has exactly n entries
- Every value and every rank fits in a signed 32-bit integer (ranks are at most m * n <= 10^5)
Examples
Input: ([[7]],)
Expected Output: [[1]]
Explanation: Minimum valid 1x1 matrix: the only cell gets rank 1.
Input: ([[-1000000000]],)
Expected Output: [[1]]
Explanation: Singleton holding the lower value bound -10^9 still gets rank 1.
Hints
- Only cells that share a row or a column constrain each other, and only the smaller values in those lines can push a cell's rank upward.
- If the ranks of all smaller cells in a cell's row and column were already known, the smallest rank that cell could take would be fixed.
- Constraints travel across lines: in Example 2, 4 sits above 2 through its row and above 1 through its column, and longer chains of such steps can raise a rank further.