Minimize maximum value in a grid

Array Union-Find Graph Theory Topological Sort Sorting Matrix

70.1% acceptance

Mar 31, 2026

144

You are given an m x n integer matrix grid containing distinct positive integers. You have to replace each integer in the matrix with a positive integer satisfying the following conditions: The relative order of every two elements that are in the same row or column should stay the same after the replacements. The maximum number in the matrix after the replacements should be as small as possible. The relative order stays the same if for all pairs of elements in the original matrix such that grid[r1][c1] > grid[r2][c2] where either r1 == r2 or c1 == c2, then it must be true that grid[r1][c1] > grid[r2][c2] after the replacements. For example, if grid = [[2, 4, 5], [7, 3, 9]] then a good replacement could be either grid = [[1, 2, 3], [2, 1, 4]] or grid = [[1, 2, 3], [3, 1, 4]]. Return the resulting matrix. If there are multiple answers, return any of them.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_score(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let m = grid.len();
    let n = grid[0].len();
    
    // Collect all cells with their values and positions, sort by value
    let mut cells: Vec<(i32, usize, usize)> = Vec::with_capacity(m * n);
    for i in 0..m {
      for j in 0..n {
        cells.push((grid[i][j], i, j));
      }
    }
    cells.sort_unstable();
    
    // Track the next available value for each row and column
    let mut row_max = vec![0i32; m];
    let mut col_max = vec![0i32; n];
    let mut result = vec![vec![0i32; n]; m];
    
    for (_, r, c) in cells {
      let val = row_max[r].max(col_max[c]) + 1;
      result[r][c] = val;
      row_max[r] = val;
      col_max[c] = val;
    }
    
    result
  }
}