1632. 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 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.

The test cases are generated so that answer is unique under the given rules.

• Time : O(n)
• Space : O(n)

class Solution {
    int getParent(vector<int>& g, int n) {
        return g[n] == n? n : g[n] = getParent(g, g[n]);
    }
    void merge(vector<int>& g, int a, int b) {
        int pa = getParent(g,a), pb = getParent(g,b);
        g[pa] = g[pb] = min(pa,pb);
    }
    vector<int> unionFind(vector<pair<int, int>>& positions) {
        vector<int> group(positions.size());
        int n = positions.size();
        unordered_map<int, vector<pair<int, int>>> rowMap, colMap;

        for(int i = 0; i < n; i++) {
            group[i] = i;
            colMap[positions[i].second].push_back({positions[i].first, i});
            rowMap[positions[i].first].push_back({positions[i].second, i});
        }

        for(int i = 0; i < n; i++) {
            if(group[i] != i) continue;
            queue<pair<int, int>> q;
            unordered_set<int> rowCheck{positions[i].first}, colCheck{positions[i].second};
            q.push({positions[i].first, positions[i].second});
            while(!q.empty()) {
                auto [y, x] = q.front(); q.pop();

                for(auto& [col, index] : rowMap[y]) {  //check row
                    if(getParent(group, index) != i) {
                        merge(group, i, index);
                        if(colCheck.count(col)) continue;
                        q.push({y,col});
                        colCheck.insert(col);
                    }
                }

                for(auto& [row, index] : colMap[x]) { //check col
                    if(getParent(group, index) != i) {
                        merge(group, i, index);
                        if(rowCheck.count(row)) continue;
                        q.push({row,x});
                        rowCheck.insert(row);
                    }
                }
            }
        }
        return group;
    }

    vector<int> getRankVector(vector<pair<int, int>>& positions, vector<int>& rowRank, vector<int>& colRank) {
        vector<int> group = unionFind(positions); //o(n)
        unordered_map<int, int> rankMap;
        for(int i = 0; i < group.size(); i++) { //o(n)
            int pi = getParent(group, i);
            rankMap[pi] = max({rankMap[pi], rowRank[positions[i].first], colRank[positions[i].second]});
        }
        for(int i = group.size() - 1; i >= 0; i--) { //o(n)
            group[i] = rankMap[getParent(group,i)];
        }
        return group;
    }
public:
    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        map<int, vector<pair<int,int>>> orderedMap;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                orderedMap[matrix[i][j]].push_back({i,j});
            }
        }
        vector<vector<int>> res(n,vector<int>(m));
        vector<int> rowRank(n, 1);
        vector<int> colRank(m, 1);
        for(auto& [value, positions] : orderedMap) {
            vector<int> rank = getRankVector(positions, rowRank, colRank);
            for(int i = 0; i < positions.size(); i++) {
                res[positions[i].first][positions[i].second] = rank[i];
                rowRank[positions[i].first] = colRank[positions[i].second] = res[positions[i].first][positions[i].second] + 1;
            }
        }
        return res;
    }
};