from collections import defaultdict
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
class Solution:
def matrixRankTransform(self, matrix):
m, n = len(matrix), len(matrix[0])
answer = [[0]*n for _ in range(m)]
value_to_positions = defaultdict(list)
for i in range(m):
for j in range(n):
value_to_positions[matrix[i][j]].append((i, j))
rank = [0] * (m + n)
for value in sorted(value_to_positions):
dsu = DSU(m + n)
for i, j in value_to_positions[value]:
dsu.union(i, j + m)
group_max_rank = {}
for i, j in value_to_positions[value]:
root = dsu.find(i)
group_max_rank[root] = max(group_max_rank.get(root, 0), rank[i], rank[j + m])
for i, j in value_to_positions[value]:
root = dsu.find(i)
answer[i][j] = group_max_rank[root] + 1
for i, j in value_to_positions[value]:
rank[i] = answer[i][j]
rank[j + m] = answer[i][j]
return answer
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class DSU {
public:
vector<int> parent;
DSU(int n) : parent(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 unite(int x, int y) {
parent[find(x)] = find(y);
}
};
class Solution {
public:
vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> answer(m, vector<int>(n, 0));
map<int, vector<pair<int,int>>> value_to_positions;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
value_to_positions[matrix[i][j]].emplace_back(i, j);
vector<int> rank(m + n, 0);
for (auto& [value, positions] : value_to_positions) {
DSU dsu(m + n);
for (auto& [i, j] : positions)
dsu.unite(i, j + m);
map<int, int> group_max_rank;
for (auto& [i, j] : positions) {
int root = dsu.find(i);
group_max_rank[root] = max(group_max_rank[root], max(rank[i], rank[j + m]));
}
for (auto& [i, j] : positions) {
int root = dsu.find(i);
answer[i][j] = group_max_rank[root] + 1;
}
for (auto& [i, j] : positions) {
rank[i] = answer[i][j];
rank[j + m] = answer[i][j];
}
}
return answer;
}
};
import java.util.*;
class DSU {
int[] parent;
DSU(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 x, int y) {
parent[find(x)] = find(y);
}
}
class Solution {
public int[][] matrixRankTransform(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] answer = new int[m][n];
Map<Integer, List<int[]>> valueToPositions = new TreeMap<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
valueToPositions.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[]{i, j});
int[] rank = new int[m + n];
for (int value : valueToPositions.keySet()) {
DSU dsu = new DSU(m + n);
for (int[] pos : valueToPositions.get(value))
dsu.union(pos[0], pos[1] + m);
Map<Integer, Integer> groupMaxRank = new HashMap<>();
for (int[] pos : valueToPositions.get(value)) {
int root = dsu.find(pos[0]);
groupMaxRank.put(root, Math.max(groupMaxRank.getOrDefault(root, 0), Math.max(rank[pos[0]], rank[pos[1] + m])));
}
for (int[] pos : valueToPositions.get(value)) {
int root = dsu.find(pos[0]);
answer[pos[0]][pos[1]] = groupMaxRank.get(root) + 1;
}
for (int[] pos : valueToPositions.get(value)) {
rank[pos[0]] = answer[pos[0]][pos[1]];
rank[pos[1] + m] = answer[pos[0]][pos[1]];
}
}
return answer;
}
}
class DSU {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
this.parent[this.find(x)] = this.find(y);
}
}
var matrixRankTransform = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const answer = Array.from({length: m}, () => Array(n).fill(0));
const valueToPositions = new Map();
for (let i = 0; i < m; ++i)
for (let j = 0; j < n; ++j) {
if (!valueToPositions.has(matrix[i][j])) valueToPositions.set(matrix[i][j], []);
valueToPositions.get(matrix[i][j]).push([i, j]);
}
let rank = Array(m + n).fill(0);
const sortedValues = Array.from(valueToPositions.keys()).sort((a, b) => a - b);
for (const value of sortedValues) {
const dsu = new DSU(m + n);
for (const [i, j] of valueToPositions.get(value))
dsu.union(i, j + m);
const groupMaxRank = {};
for (const [i, j] of valueToPositions.get(value)) {
const root = dsu.find(i);
groupMaxRank[root] = Math.max(groupMaxRank[root] || 0, rank[i], rank[j + m]);
}
for (const [i, j] of valueToPositions.get(value)) {
const root = dsu.find(i);
answer[i][j] = groupMaxRank[root] + 1;
}
for (const [i, j] of valueToPositions.get(value)) {
rank[i] = answer[i][j];
rank[j + m] = answer[i][j];
}
}
return answer;
};
Given an integer matrix matrix of size m x n, your task is to transform the matrix so that each element is replaced by its rank. The rank of an element is defined as follows:
The output is a new matrix of the same size, where each position contains the computed rank for the corresponding element of the input.
The problem at first glance may seem similar to sorting or ranking elements, but the twist is that the rank must respect both the row and column dependencies, and identical values connected in a row or column must have the same rank.
A brute-force approach would be to repeatedly scan the matrix, updating ranks whenever a constraint is violated, but this would be very inefficient. Instead, we need to process the elements in value order, ensuring that smaller values are ranked before larger ones, and that all constraints are maintained.
The main challenge is managing the dependencies between rows and columns, especially for duplicate values. Using a data structure that can efficiently group connected elements with the same value (like Union-Find/Disjoint Set Union) is key for handling this efficiently.
To solve the problem efficiently, we use the following steps:
By using a DSU, we efficiently manage connections between duplicate values, and by processing in value order, we guarantee that all constraints are met.
Consider the matrix:
1 2
3 4
The resulting matrix is:
1 2
2 3
If there are duplicate values in the same row or column, they are grouped and assigned the same rank.
The Rank Transform of a Matrix problem is solved efficiently by processing elements in value order, using Union-Find to group duplicates, and carefully tracking the maximum rank in each row and column. This approach ensures all constraints are met and achieves optimal time complexity. The elegance comes from combining sorting, grouping, and DSU to handle all dependencies succinctly.