Rank Transform of a Matrix
Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].
The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:
- The rank is an integer starting from
1. - If two elements
pandqare in the same row or column, then: - If
p < qthenrank(p) < rank(q). - If
p == qthenrank(p) == rank(q). - If
p > qthenrank(p) > rank(q). - The rank should be as small as possible.
The test cases are generated so that answer is unique under the given rules.
Example 1
1 2 3 4
Input
matrix = [[1,2],[3,4]]Output
[[1,2],[2,3]]The smallest element in the first row and column has rank 1, the adjacent larger elements have rank 2, and the largest bottom-right element has rank 3.
Example 2
7 7 7 7
Input
matrix = [[7,7],[7,7]]Output
[[1,1],[1,1]]All elements are equal and connected by rows or columns, so they all receive the same smallest possible rank 1.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 500
- -10^9 <= matrix[row][col] <= 10^9