1632

1632. Rank Transform of a Matrix (Hard)

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 p and q are in the same row or column, then:
  • If p < q then rank(p) < rank(q)
  • If p == q then rank(p) == rank(q)
  • If p > q then rank(p) > rank(q)
• The rank should be as small as possible.

It is guaranteed that answer is unique under the given rules.

 

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.

Example 2:

Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]

Example 3:

Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

Example 4:

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

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 500
• -109 <= matrix[row][col] <= 109

Related Topics:
Greedy, Union Find

Similar Questions:

• Rank Transform of an Array (Easy)

Solution 1. Union Find

Intuition: Sort the numbers in ascending order. Visit them one by one. Each number should have a rank that is greater than those smaller numbers in the same row/column that are already assigned ranks.

The tricky part is how to handle those numbers of the same value. The numbers that have the same value and are in the same row/column should use the same rank, and the rank is the greatest one of those ranks if we check them individually.

To group those numbers, we can use Union Find.

If two numbers in the same row share the same value, we should connect the two column indexes.

If two numbers in the same column share the same value, we should connect the two row indexes.

Basically we are regarding the row and column indexes as vertices in a graph, and the numbers in the matrix as edge.

Time complexity:

For pushing into the map, in the worst case where all the numbers are different, the map will have MN distinct values, so it's O(MNlog(MN)).

For each of the loops with Union Find, the time complexity is O(K) where K is the count of the pos array. So the overall time complexity of the Union Find loop is O(MN).

In sum, the time complexity is O(MNlog(MN)).

// OJ: https://leetcode.com/problems/rank-transform-of-a-matrix/
// Author: github.com/lzl124631x
// Time: O(MNlog(MN))
// Space: O(MN)
// Ref: https://leetcode.com/problems/rank-transform-of-a-matrix/discuss/909142/Python-Union-Find
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    void connect(int a, int b) {
        int x = find(a), y = find(b);
        if (x == y) return;
        id[x] = y;
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
};
class Solution {
public:
    vector<vector<int>> matrixRankTransform(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        map<int, vector<vector<int>>> m;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) m[A[i][j]].push_back({ i, j });
        }
        vector<int> rank(M + N, 0); // rank[0..(M-1)] stores the highest ranks of the rows, rank[M..(M+N-1)] stores the highest ranks of the columns.
        vector<vector<int>> ans(M, vector<int>(N));
        for (auto &[val, pos] : m) {
            UnionFind uf(M + N);
            for (auto &p : pos) {
                int x = uf.find(p[0]), y = uf.find(p[1] + M);
                uf.connect(x, y); // for each number, connect its (representative) row and column
                rank[uf.find(x)] = max(rank[x], rank[y]);
            }
            auto next = rank;
            for (auto &p : pos) {
                int x = p[0], y = p[1], r = uf.find(x);
                ans[x][y] = next[x] = next[y + M] = rank[r] + 1;
            }
            rank = move(next);
        }
        return ans;
    }
};