Problem
Given an m x n integer matrix, assign a rank to every element.The rank must satisfy these rules: a rank is a positive integer, and if two elements are in the same row or column, the smaller value must have a smaller rank. If two equal values are in the same row or column, they must have the same rank.
The rank of an element should be as small as possible while satisfying all these conditions.
Example(s)
Example 1
Input
matrix = [[1,2], [3,4]]Output
[[1,2], [2,3]]Example 2
Input
matrix = [[7,7], [7,7]]Output
[[1,1], [1,1]]Solution
This problem uses Union-Find with Sorting. Process matrix values in ascending order. For equal values, connect all cells having the same value when they share a row or column using Union-Find.For each connected group, its rank is determined by the maximum rank already assigned to the corresponding rows and columns. After calculating the rank for the group, update the row and column ranks.
class Solution {
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] result = new int[m][n];
Map<Integer, List<int[]>> groups = new TreeMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
groups.computeIfAbsent(matrix[i][j], k -> new ArrayList<>())
.add(new int[]{i, j});
}
}
int[] rowRank = new int[m];
int[] columnRank = new int[n];
for (List<int[]> cells : groups.values()) {
int size = cells.size();
UnionFind uf = new UnionFind(size);
Map<Integer, Integer> rowOwner = new HashMap<>();
Map<Integer, Integer> columnOwner = new HashMap<>();
for (int i = 0; i < size; i++) {
int row = cells.get(i)[0];
int column = cells.get(i)[1];
if (rowOwner.containsKey(row)) {
uf.union(i, rowOwner.get(row));
} else {
rowOwner.put(row, i);
}
if (columnOwner.containsKey(column)) {
uf.union(i, columnOwner.get(column));
} else {
columnOwner.put(column, i);
}
}
Map<Integer, Integer> rank = new HashMap<>();
for (int i = 0; i < size; i++) {
int root = uf.find(i);
int row = cells.get(i)[0];
int column = cells.get(i)[1];
rank.put(
root,
Math.max(
rank.getOrDefault(root, 0),
Math.max(rowRank[row], columnRank[column])
)
);
}
for (int i = 0; i < size; i++) {
int root = uf.find(i);
int row = cells.get(i)[0];
int column = cells.get(i)[1];
int value = rank.get(root) + 1;
result[row][column] = value;
rowRank[row] = Math.max(rowRank[row], value);
columnRank[column] = Math.max(columnRank[column], value);
}
}
return result;
}
private class UnionFind {
int[] parent;
UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
parent[rootB] = rootA;
}
}
}
}