Rank Every Cell of a Distinct-Value Matrix Consistently Within Its Row and Column

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

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

Input: matrix = [[10, 40, 20, 30]]
Output: [[1, 4, 2, 3]]

Example 2

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

Input: matrix = [
 [3, 1, 9],
 [8, 2, 7],
 [4, 6, 5]
]
Output: [
 [2, 1, 6],
 [6, 2, 5],
 [3, 5, 4]
]