Rank transform of a matrix

Array Union-Find Graph Theory Topological Sort Sorting Matrix

42.1% acceptance

Feb 25, 2026

930

Given an m x 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn matrix_rank_transform(matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut ans = vec![vec![0i32; n]; m];
    let mut row_max = vec![0i32; m];
    let mut col_max = vec![0i32; n];

    // Collect all (val, r, c) sorted by val
    let mut cells: Vec<(i32, usize, usize)> = Vec::new();
    for r in 0..m {
      for c in 0..n {
        cells.push((matrix[r][c], r, c));
      }
    }
    cells.sort();

    let mut i = 0;
    while i < cells.len() {
      let val = cells[i].0;
      let mut j = i;
      while j < cells.len() && cells[j].0 == val { j += 1; }
      let group = &cells[i..j];

      // Union-Find over cells in this group: connect same row or col
      let size = group.len();
      let mut parent: Vec<usize> = (0..size).collect();

      fn find(parent: &mut Vec<usize>, x: usize) -> usize {
        if parent[x] != x { parent[x] = find(parent, parent[x]); }
        parent[x]
      }

      // Map row -> list of group indices, col -> list of group indices
      let mut row_map: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
      let mut col_map: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();

      for k in 0..size {
        let (_, r, c) = group[k];
        if let Some(&prev) = row_map.get(&r) {
          let pr = find(&mut parent, prev);
          let pk = find(&mut parent, k);
          if pr != pk { parent[pr] = pk; }
        }
        row_map.insert(r, k);
        if let Some(&prev) = col_map.get(&c) {
          let pr = find(&mut parent, prev);
          let pk = find(&mut parent, k);
          if pr != pk { parent[pr] = pk; }
        }
        col_map.insert(c, k);
      }

      // For each component, compute rank = 1 + max(row_max, col_max) for all cells
      let mut comp_rank: std::collections::HashMap<usize, i32> = std::collections::HashMap::new();
      for k in 0..size {
        let (_, r, c) = group[k];
        let root = find(&mut parent, k);
        let e = comp_rank.entry(root).or_insert(0);
        *e = (*e).max(row_max[r]).max(col_max[c]);
      }

      // Assign ranks
      for k in 0..size {
        let (_, r, c) = group[k];
        let root = find(&mut parent, k);
        let rank = comp_rank[&root] + 1;
        ans[r][c] = rank;
        row_max[r] = row_max[r].max(rank);
        col_max[c] = col_max[c].max(rank);
      }

      i = j;
    }
    ans
  }
}