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]
]

Minimal Rank Transform of a Distinct-Valued Matrix

Hints

1. 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.
2. 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.
3. 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.

Approach

Sort the cells by value and visit them in increasing order, keeping row_best[r] and col_best[c]: the largest rank already assigned in row r and in column c (initially 0). When cell (i, j) is visited, every smaller cell in row i or column j has already been ranked, and row_best[i] and col_best[j] hold the largest of those ranks. The rules require the cell's rank to exceed every one of them and impose nothing else, so its smallest valid rank is max(row_best[i], col_best[j]) + 1. Assign it, then set row_best[i] and col_best[j] to it (it is larger than both old values).

Invariant: after the k smallest values are processed, each has its minimal rank, and row_best / col_best hold the maximum rank among processed cells of each row and column. Correctness: a cell's minimal rank equals the number of cells on the longest strictly increasing chain that ends at it, where consecutive cells share a row or a column. By induction over the sorted order, the assigned rank equals that length, and the assignment satisfies every rule because each later, larger cell is placed strictly above the current maximum of both of its lines. Values are distinct, so no two cells in a line tie and no grouping is needed.

Edge cases: a 1x1 matrix gives [[1]]; a single row or a single column reduces to sorted positions; minima that share no row or column (for example along a diagonal) all get rank 1; and a chain that alternates rows and columns can push a rank up to m * n, as in [[1, 2], [4, 3]] -> [[1, 2], [4, 3]].

• Time complexity: O(m * n * log(m * n))
• Space complexity: O(m * n)