Editorial: LeetCode 1632 Rank Transform of a Matrix
https://leetcode.com/problems/rank-transform-of-a-matrix/ from Google
Thinking process:
This one is really hard. It’s very easy to figure out that we need to sort the element first. However, when dealing with this condition If p == q then rank(p) == rank(q), there are many edge cases. If there are two elements with the same value and sharing the same row or column, then their rank should be the same, otherwise, their rank will be the (max rank in their row and column) + 1.
So, the question now becomes: how can I join those elements together if they share the same row or column. This sounds like we need a 2-D union-find?! But if we think carefully, for any element (x, y), we only need to join x and y together. (x1, y1) and (x2, y2) will be joined automatically if they share a row or a column. Thus, this become a normal union-find. We just need to shift column index a little bit.
Below is the code.
1class Solution {
2public:
3 vector<int> p;
4 int f(int x) {
5 if (p[x] == x) return x;
6 return p[x] = f(p[x]);
7 }
8 vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
9 vector<vector<int>> all;
10 int R = matrix.size();
11 int C = matrix[0].size();
12 map<int, vector<pair<int, int>>> m;
13 p.resize(R+C);
14 for (int i=0; i<R; i++) {
15 for (int j=0; j<C; j++) {
16 m[matrix[i][j]].push_back({i, j});
17 }
18 }
19 vector<vector<int>> ans(R, vector<int>(C));
20 vector<int> Max(R+C);
21 vector<int> rmax(R);
22 vector<int> cmax(C);
23 for (auto &it : m) {
24 for (auto &it2 : it.second) {
25 // Don't want to reset the whole parent everytime
26 // We just need to reset the rows and columns
27 // we're going to use this time
28 p[it2.first] = it2.first;
29 Max[it2.first] = rmax[it2.first];
30 p[it2.second+R] = it2.second+R;
31 Max[it2.second+R] = cmax[it2.second];
32 }
33 for (auto &it2 : it.second) {
34 // Union row and column together
35 // Also the max rank
36 int a = f(it2.first), b = f(it2.second+R);
37 if (a != b) {
38 p[a] = b;
39 Max[b] = max(Max[a], Max[b]);
40 }
41 }
42 // Perform update in another loop since we only
43 // know the max rank after union-find
44 for (auto &it2 : it.second) {
45 int x = Max[f(it2.first)]+1;
46 ans[it2.first][it2.second] = x;
47 rmax[it2.first] = x;
48 cmax[it2.second] = x;
49 }
50 }
51 return ans;
52 }
53};