LeetCode 1632: Rank Transform of a Matrix in Rust

Question

This is a problem-solving code for LeetCode 1632.

Given an \$m \times 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.

It is guaranteed that answer is unique under the given rules.

The code is translated from C++, which has several similar code blocks in the function matrix_rank_transform. It seems that we can simplify it but it's not very straightforward, for the first block it scans the matrix with row first, for the second one, it scans the matrix with column first, any suggestions will be welcome!

type LenthType = u32;
struct UnionFind {
 ancestor: Vec<LenthType>,
 size: Vec<LenthType>,
}
impl UnionFind {
 pub fn new(n: usize) -> UnionFind {
 UnionFind {
 ancestor: (0..n as LenthType).collect(),
 size: vec![1; n],
 }
 }
 pub fn union(&mut self, index_1: usize, index_2: usize) {
 let (root_1, root_2) = (self.root(index_1), self.root(index_2));
 if root_1 == root_2 {
 return;
 }
 if self.size[root_1] > self.size[root_2] {
 self.ancestor[root_2] = root_1 as LenthType;
 self.size[root_1] += self.size[root_2];
 } else {
 self.ancestor[root_1] = root_2 as LenthType;
 self.size[root_2] += self.size[root_1];
 }
 }
 pub fn root(&mut self, mut index: usize) -> usize {
 while index != self.ancestor[index] as usize {
 self.ancestor[index] = self.ancestor[self.ancestor[index] as usize];
 index = self.ancestor[index] as usize;
 }
 index
 }
}
use std::collections::{HashMap, VecDeque};
impl Solution {
 pub fn matrix_rank_transform(matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
 let (row, col) = (matrix.len(), matrix[0].len());
 let mut union_find = UnionFind::new(row * col);
 for i in 0..row {
 let mut map = HashMap::new();
 for j in 0..col {
 map.entry(matrix[i][j])
 .or_insert(Vec::new())
 .push(i * col + j);
 }
 for (_key, val) in map {
 for k in 0..(val.len() - 1) {
 union_find.union(val[k], val[k + 1]);
 }
 }
 }
 for j in 0..col {
 let mut map = HashMap::new();
 for i in 0..row {
 map.entry(matrix[i][j])
 .or_insert(Vec::new())
 .push(i * col + j);
 }
 for (_key, val) in map {
 for k in 0..(val.len() - 1) {
 union_find.union(val[k], val[k + 1]);
 }
 }
 }
 let mut adj_list = vec![Vec::new(); row * col];
 let mut in_degree = vec![0; row * col];
 for i in 0..row {
 let mut vec_pair = vec![(0, 0); col];
 for j in 0..col {
 vec_pair[j] = (matrix[i][j], j);
 }
 vec_pair.sort();
 for j in 0..(col - 1) {
 if vec_pair[j].0 != vec_pair[j + 1].0 {
 let u_root = union_find.root(i * col + vec_pair[j].1);
 let v_root = union_find.root(i * col + vec_pair[j + 1].1);
 adj_list[u_root].push(v_root);
 in_degree[v_root] += 1;
 }
 }
 }
 for j in 0..col {
 let mut vec_pair = vec![(0, 0); row];
 for i in 0..row {
 vec_pair[i] = (matrix[i][j], i);
 }
 vec_pair.sort();
 for i in 0..(row - 1) {
 if vec_pair[i].0 != vec_pair[i + 1].0 {
 let u_root = union_find.root(vec_pair[i].1 * col + j);
 let v_root = union_find.root(vec_pair[i + 1].1 * col + j);
 adj_list[u_root].push(v_root);
 in_degree[v_root] += 1;
 }
 }
 }
 let mut ans = vec![1; row * col];
 let mut queue = VecDeque::new();
 for i in 0..row * col {
 if union_find.root(i) == i && in_degree[i] == 0 {
 queue.push_back(i);
 }
 }
 while let Some(node) = queue.pop_back() {
 for &v in &adj_list[node] {
 ans[v] = ans[v].max(ans[node] + 1);
 in_degree[v] -= 1;
 if in_degree[v] == 0 {
 queue.push_back(v);
 }
 }
 }
 let mut result = vec![vec![0; col]; row];
 for i in 0..row {
 for j in 0..col {
 result[i][j] = ans[union_find.root(i * col + j)];
 }
 }
 result
 }
}
struct Solution;
fn main() {
 assert_eq!(
 Solution::matrix_rank_transform(vec![vec![1, 2], vec![3, 4]]),
 vec![vec![1, 2], vec![2, 3]]
 );
 assert_eq!(
 Solution::matrix_rank_transform(vec![
 vec![-37, -26, -47, -40, -13],
 vec![22, -11, -44, 47, -6],
 vec![-35, 8, -45, 34, -31],
 vec![-16, 23, -6, -43, -20],
 vec![47, 38, -27, -8, 43]
 ]),
 vec![
 vec![3, 4, 1, 2, 7],
 vec![9, 5, 3, 10, 8],
 vec![4, 6, 2, 7, 5],
 vec![7, 9, 8, 1, 6],
 vec![12, 10, 4, 5, 11]
 ]
 );
}

• L. F.: Can you add a description of the purpose of the code?