Rank every cell of a matrix of distinct values

You get an m x n matrix of distinct integers. Replace every value with its rank: ranks start at 1; for two cells in the same row or the same column, the larger value has a strictly larger rank; and every rank is as small as possible under those rules. Because the values are distinct, the answer is unique.

Interface

Unless you agree on a different interface with the interviewer, assume:

• matrix_ranks(matrix: list[list[int]]) -> list[list[int]] — returns a matrix of the same shape holding the ranks.

Example

matrix_ranks([[10, 40, 20, 30]])  ->  [[1, 4, 2, 3]]      # one row: plain ranking

matrix_ranks([[1, 5],
              [4, 2]])            ->  [[1, 2],
                                       [2, 1]]
    # 1 and 2 share no row or column, so both get rank 1; 4 and 5 each sit above a rank-1 cell

matrix_ranks([[3, 1, 9],
              [8, 2, 7],
              [4, 6, 5]])         ->  [[2, 1, 6],
                                       [6, 2, 5],
                                       [3, 5, 4]]

Constraints

• 1 <= m, n <= 500, m * n <= 10^5.
• -10^9 <= matrix[i][j] <= 10^9, all distinct.

Clarifying questions

• Do only cells in the same row or column constrain each other?
• Are the values guaranteed distinct, or must equal values in a line share a rank?
• What does "as small as possible" mean when constraints chain across rows and columns?

What a strong answer covers

• Process cells in increasing value. Keep the largest rank given so far in each row and each column; a cell's rank is one more than the larger of its row's and its column's maximum. Then update both.
• Why this is correct: every smaller value in the cell's lines already has its final rank, and the cell needs to exceed only those.
• O(mn log(mn)) for the sort, O(m + n) extra state.
• Tests: one row, one column, a 1 x 1 matrix, chains where a rank rises through several lines (Example 3).

Follow-ups

• Values may repeat, and equal values in the same row or column must get the same rank (needs union-find over equal values).
• Return only the largest rank in the matrix.
• The matrix is updated one cell at a time: how much needs recomputing?