1import java.util.*;
2
3class UnionFind {
4    private int[] parent;  // Array to hold the representative (parent) for each element
5    private int[] size;    // Array to hold the size of each set
6
7    public UnionFind(int capacity) {
8        parent = new int[capacity];
9        size = new int[capacity];
10        for (int i = 0; i < capacity; ++i) {
11            parent[i] = i;  // Initially, each element is its own parent (self-loop)
12            size[i] = 1;    // And the size of each set is one
13        }
14    }
15
16    // Find the representative of the set that element x is part of
17    public int find(int x) {
18        if (parent[x] != x) {
19            parent[x] = find(parent[x]);  // Path compression heuristic
20        }
21        return parent[x];
22    }
23
24    // Unify the sets that elements `a` and `b` are part of
25    public void union(int a, int b) {
26        int rootA = find(a);
27        int rootB = find(b);
28        if (rootA != rootB) {
29            // Merge by size heuristic: smaller set points to the larger one
30            if (size[rootA] > size[rootB]) {
31                parent[rootB] = rootA;
32                size[rootA] += size[rootB];
33            } else {
34                parent[rootA] = rootB;
35                size[rootB] += size[rootA];
36            }
37        }
38    }
39
40    // Reset the representative and size for the element `x`
41    public void reset(int x) {
42        parent[x] = x;
43        size[x] = 1;
44    }
45}
46
47class Solution {
48    public int[][] matrixRankTransform(int[][] matrix) {
49        int height = matrix.length;       // Number of rows in matrix
50        int width = matrix[0].length;     // Number of columns in matrix
51      
52        // Mapping values to their indices in the matrix
53        TreeMap<Integer, List<int[]>> valueToIndices = new TreeMap<>();
54      
55        // Store the indices of each value in the matrix
56        for (int i = 0; i < height; ++i) {
57            for (int j = 0; j < width; ++j) {
58                valueToIndices.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[] {i, j});
59            }
60        }
61      
62        // Arrays holding the max rank in each row and column
63        int[] rowMax = new int[height];
64        int[] colMax = new int[width];
65        // The matrix to hold the final rank transformation
66        int[][] rankTransform = new int[height][width];
67      
68        // Union-find structure for rows and columns
69        UnionFind unionFind = new UnionFind(height + width);
70        // Array holding the rank of each element in the union-find structure
71        int[] rank = new int[height + width];
72      
73        // Process the values in ascending order
74        for (var positions : valueToIndices.values()) {
75            // Union all positions with the same value
76            for (var position : positions) {
77                unionFind.union(position[0], position[1] + height);
78            }
79            // Compute the rank for each union-find root
80            for (var position : positions) {
81                int row = position[0], col = position[1];
82                rank[unionFind.find(row)] = Math.max(rank[unionFind.find(row)], Math.max(rowMax[row], colMax[col]));
83            }
84            // Assign the rank to the positions and update the max row and column ranks
85            for (var position : positions) {
86                int row = position[0], col = position[1];
87                rankTransform[row][col] = 1 + rank[unionFind.find(row)];
88                rowMax[row] = rankTransform[row][col];
89                colMax[col] = rankTransform[row][col];
90            }
91            // Reset the union-find structure for the next value
92            for (var position : positions) {
93                unionFind.reset(position[0]);
94                unionFind.reset(position[1] + height);
95            }
96        }
97        return rankTransform;
98    }
99}
100

1#include <vector>
2#include <map>
3#include <numeric>
4using namespace std;
5
6// Union-Find class to manage disjoint sets operations.
7class UnionFind {
8public:
9    // Constructor initializes the union-find structure.
10    UnionFind(int n) {
11        parents.resize(n);
12        sizes.resize(n, 1);
13        iota(parents.begin(), parents.end(), 0);  // Set each element to be its own parent.
14    }
15
16    // Unite two subsets into a single subset if they are different.
17    void unite(int a, int b) {
18        int rootA = find(a), rootB = find(b);
19        if (rootA != rootB) {
20            // Join the two trees by size. Attach the smaller tree to the larger one.
21            if (sizes[rootA] > sizes[rootB]) {
22                parents[rootB] = rootA;
23                sizes[rootA] += sizes[rootB];
24            } else {
25                parents[rootA] = rootB;
26                sizes[rootB] += sizes[rootA];
27            }
28        }
29    }
30
31    // Find the root parent of a node. Path compression is applied.
32    int find(int x) {
33        if (parents[x] != x) {
34            parents[x] = find(parents[x]);  // Path compression for efficiency.
35        }
36        return parents[x];
37    }
38
39    // Resets a node to be a standalone subset.
40    void reset(int x) {
41        parents[x] = x;
42        sizes[x] = 1;
43    }
44
45private:
46    vector<int> parents; // Contains parent/representative for each node.
47    vector<int> sizes;   // Size of each set (used to keep trees balanced).
48};
49
50class Solution {
51public:
52    // Transform the given matrix so that each element is the smallest rank greater than all elements with a smaller value in its row and column.
53    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
54        int m = matrix.size(), n = matrix[0].size();
55        map<int, vector<pair<int, int>>> valueToCoordinates;
56
57        // Group cells by their values in the matrix.
58        for (int i = 0; i < m; ++i) {
59            for (int j = 0; j < n; ++j) {
60                valueToCoordinates[matrix[i][j]].emplace_back(i, j);
61            }
62        }
63
64        vector<int> rowMax(m, 0); // Max rank of each row.
65        vector<int> colMax(n, 0); // Max rank of each column.
66        vector<vector<int>> answer(m, vector<int>(n, 0)); // Store ranks for answer.
67        UnionFind unionFind(m + n); // Union-find instance for rows and columns.
68        vector<int> rank(m + n, 0); // Rank of each combined set of row and column.
69
70        // Iterate over groups of cells by ascending values.
71        for (auto& [value, cells] : valueToCoordinates) {
72            // Unite rows and columns of cells with same value.
73            for (auto& [row, col] : cells) {
74                unionFind.unite(row, col + m);
75            }
76
77            // Compute the maximum rank for each set.
78            for (auto& [row, col] : cells) {
79                int root = unionFind.find(row);
80                rank[root] = max({rank[root], rowMax[row], colMax[col]});
81            }
82
83            // Update the ranks in the answer matrix and update row/column max ranks.
84            for (auto& [row, col] : cells) {
85                answer[row][col] = rowMax[row] = colMax[col] = rank[unionFind.find(row)] + 1;
86            }
87
88            // Reset the union-find structure for the next value.
89            for (auto& [row, col] : cells) {
90                unionFind.reset(row);
91                unionFind.reset(col + m);
92            }
93        }
94
95        return answer; // Return the rank-transformed matrix.
96    }
97};
98

1// Represents each node's parent and size for Union-Find operations
2let parents: number[];
3let sizes: number[];
4
5// Initializes the Union-Find structure with `n` elements.
6function initializeUnionFind(n: number): void {
7    parents = Array.from({length: n}, (_, index) => index); 
8    sizes = new Array(n).fill(1);
9}
10
11// Finds the root of the set that element `x` belongs to.
12function find(x: number): number {
13    if (parents[x] !== x) {
14        parents[x] = find(parents[x]); // Path compression
15    }
16    return parents[x];
17}
18
19// Unites the sets to which elements `a` and `b` belong.
20function unite(a: number, b: number): void {
21    const rootA = find(a);
22    const rootB = find(b);
23    if (rootA !== rootB) {
24        // Attach the smaller tree to the larger one.
25        if (sizes[rootA] > sizes[rootB]) {
26            parents[rootB] = rootA;
27            sizes[rootA] += sizes[rootB];
28        } else {
29            parents[rootA] = rootB;
30            sizes[rootB] += sizes[rootA];
31        }
32    }
33}
34
35// Resets the subset that includes `x` to be standalone.
36function reset(x: number): void {
37    parents[x] = x;
38    sizes[x] = 1;
39}
40
41// Transforms the input `matrix` based on the problem statement.
42function matrixRankTransform(matrix: number[][]): number[][] {
43    const m = matrix.length;
44    const n = matrix[0].length;
45    const valueToCoordinates: Map<number, Array<[number, number]>> = new Map();
46
47    // Group cells by their values
48    for (let i = 0; i < m; ++i) {
49        for (let j = 0; j < n; ++j) {
50            if (!valueToCoordinates.has(matrix[i][j])) {
51                valueToCoordinates.set(matrix[i][j], []);
52            }
53            valueToCoordinates.get(matrix[i][j])!.push([i, j]);
54        }
55    }
56
57    const rowMax = new Array(m).fill(0); // Max rank of each row
58    const colMax = new Array(n).fill(0); // Max rank of each column
59    const answer = Array.from({length: m}, () => new Array(n).fill(0)); // Initialized rank matrix
60
61    // Process coordinates grouped by value
62    for (const [value, cells] of valueToCoordinates) {
63        initializeUnionFind(m + n); // Union-find for rows and columns
64        const rank = new Array(m + n).fill(0); // Rank for each set
65
66        // Union rows and columns
67        for (const [row, col] of cells) {
68            unite(row, col + m);
69        }
70
71        // Find the max rank for the current set of cells
72        for (const [row, col] of cells) {
73            const root = find(row);
74            rank[root] = Math.max(rank[root], rowMax[row], colMax[col]);
75        }
76
77        // Assign ranks to the answer matrix, update rowMax and colMax
78        for (const [row, col] of cells) {
79            const rootRank = rank[find(row)] + 1;
80            answer[row][col] = rootRank;
81            rowMax[row] = colMax[col] = rootRank;
82        }
83      
84        // No need to reset Union-Find because it's reinitialized at the beginning of each value group
85    }
86
87    return answer; // Return the rank-transformed matrix
88}
89