hardGraphsPure DSA~50 min
Assign Ranks Preserving Row and Column Order
Normalize a metric matrix into ranks: the smallest distinct value is rank 1, and ranks must respect ordering within each row and each column while keeping equal values that are connected at the same rank.
Problem
Given an m x n matrix, return a matrix answer where answer[i][j] is the rank of matrix[i][j]. Rank is at least 1; if two elements are in the same row or column, the smaller gets the lower rank and equal elements connected through shared rows/columns get the same rank; ranks should be as small as possible.
Input
An m x n integer matrix.
Output
An m x n integer matrix of ranks.
Constraints
- 1 <= m, n <= 500
- -10^9 <= matrix[i][j] <= 10^9
- Equal values may appear anywhere.
Examples
Example 1
Input
matrix = [[1,2],[3,4]]
Output
[[1,2],[2,3]]
Ranks increase along rows and columns; the 2 and 3 tie at rank 2.
Example 2
Input
matrix = [[7,7],[7,7]]
Output
[[1,1],[1,1]]
All equal and connected, so they share rank 1.