Rank of a Matrix - Google Top Interview Questions

                        Solution in C++ :

pair<int, int> find(vector<vector<pair<int, int>>>& parent, pair<int, int> ele) {
    auto [x, y] = ele;
    if (parent[x][y] == ele) return ele;
    return parent[x][y] = find(parent, parent[x][y]);
}

// this function does the union of two elements who have same value and share either the row or
// column.
void unio(vector<vector<pair<int, int>>>& parent, pair<int, int>& a, pair<int, int> b) {
    auto [x1, y1] = find(parent, a);
    auto [x2, y2] = find(parent, b);
    if (x1 == x2 and y1 == y2) {
        return;
    }
    parent[x1][y1] = {x2, y2};
}
vector<vector<int>> solve(vector<vector<int>>& nums) {
    int n = nums.size(), m = nums[0].size();

    // here we create a parent array with each element pointing to itself.
    vector<vector<pair<int, int>>> parent(n, vector<pair<int, int>>(m));

    // for keeping the highest rank's in rows and columns.
    vector<int> row(n, 0), col(m, 0);

    // initializing the dsu
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            parent[i][j] = {i, j};
        }
    }

    // union all the element which share the common row and have equal values.
    for (int i = 0; i < n; i++) {
        unordered_map<int, pair<int, int>> rows;
        for (int j = 0; j < m; j++) {
            if (rows.find(nums[i][j]) != rows.end()) {
                unio(parent, rows[nums[i][j]], {i, j});
            }
            rows[nums[i][j]] = {i, j};
        }
    }

    // union all the element which share the common columns and have equal values
    for (int j = 0; j < m; j++) {
        unordered_map<int, pair<int, int>> cols;
        for (int i = 0; i < n; i++) {
            if (cols.find(nums[i][j]) != cols.end()) {
                unio(parent, cols[nums[i][j]], {i, j});
            }
            cols[nums[i][j]] = {i, j};
        }
    }

    // now let's make the actual parent mapping. means all the element point to their real parents.
    vector<vector<pair<int, int>>> parentmapping(n, vector<pair<int, int>>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            parentmapping[i][j] = find(parent, {i, j});
        }
    }

    // now let's make the reverse parent mapping where all the elements which are in a connected
    // component can be identified.
    map<pair<int, int>, vector<pair<int, int>>> rev_mapping;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            rev_mapping[parentmapping[i][j]].push_back({i, j});
        }
    }
    // so far all the job done for finding the connected component's

    // now we start picking the element from the smaller values so we put them in a temporary array
    // and start picking the smaller values first.
    vector<vector<int>> temp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            temp.push_back({nums[i][j], i, j});
        }
    }
    sort(temp.begin(), temp.end());

    // this is the array we return
    vector<vector<int>> ret(n, vector<int>(m, 0));

    // let's start giving the ranks.
    vector<vector<int>> visited(n, vector<int>(m, 0));
    for (int i = 0; i < temp.size(); i++) {
        int vals = temp[i][0], x = temp[i][1], y = temp[i][2];

        // if this element has been already ranked we skip the element.
        if (visited[x][y] == 1) continue;

        // now we find the max rank that has been given to the elements which share the common rows
        // and colums to the elements of the connected componenets.
        int max_rank_so_far = 0;
        pair<int, int> its_parent = parentmapping[x][y];
        for (auto& nbrs : rev_mapping[its_parent]) {
            max_rank_so_far = max({max_rank_so_far, row[nbrs.first], col[nbrs.second]});
        }
        // we give the {final rank} as {max rank + 1}.
        int f_rank = max_rank_so_far + 1;
        // here we give the ranks to the elements and marked them as visited.
        for (auto [p, q] : rev_mapping[its_parent]) {
            visited[p][q] = 1;
            row[p] = col[q] = ret[p][q] = f_rank;
        }
    }
    return ret;
}
                    

                        Solution in Python : 
                            
class UnionFind:
    def __init__(self):
        self._parent = {}
        self._size = {}
        self._max_rank = {}

    def union(self, a, b, rank):
        a, b = self.find(a), self.find(b)
        if a == b:
            return
        if self._size[a] < self._size[b]:
            a, b = b, a
        self._parent[b] = a
        self._size[a] += self._size[b]
        self._max_rank[a] = max(self._max_rank[a], self._max_rank[b], rank)

    def find(self, x):
        if x not in self._parent:
            self._parent[x] = x
            self._size[x] = 1
            self._max_rank[x] = 0
            return x

        while self._parent[x] != x:
            self._parent[x] = self._parent[self._parent[x]]
            x = self._parent[x]
        return x

    def max_rank(self, x):
        return self._max_rank[self.find(x)]


class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return matrix

        m, n = len(matrix), len(matrix[0])
        groups = defaultdict(list)

        for y, row in enumerate(matrix):
            for x, val in enumerate(row):
                groups[val].append((y, x))

        A = [[0] * n for _ in range(m)]
        row_rank = [0] * m
        col_rank = [0] * n

        for val in sorted(groups):
            uf = UnionFind()
            for y, x in groups[val]:
                uf.union(y, ~x, max(row_rank[y], col_rank[x]))
            for y, x in groups[val]:
                A[y][x] = row_rank[y] = col_rank[x] = uf.max_rank(y) + 1

        return A