Minimum absolute difference in sliding submatrix

Array Sorting Matrix

68.8% acceptance

Feb 25, 2026

Given an m x n integer matrix grid and integer k, for every k x k submatrix compute the minimum absolute difference between any two distinct values within it. Return a 2D array of size (m-k+1)x(n-k+1).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_abs_diff(grid: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
    let k = k as usize;
    let m = grid.len();
    let n = grid[0].len();
    let rows_out = m - k + 1;
    let cols_out = n - k + 1;
    let mut ans = vec![vec![0i32; cols_out]; rows_out];

    for i in 0..rows_out {
      for j in 0..cols_out {
        // Collect all values in submatrix [i..i+k][j..j+k]
        let mut vals: Vec<i32> = Vec::with_capacity(k * k);
        for r in i..i + k {
          for c in j..j + k {
            vals.push(grid[r][c]);
          }
        }
        vals.sort_unstable();
        vals.dedup();
        if vals.len() < 2 {
          ans[i][j] = 0;
        } else {
          let mut min_diff = i32::MAX;
          for idx in 1..vals.len() {
            let d = vals[idx] - vals[idx - 1];
            if d < min_diff {
              min_diff = d;
            }
          }
          ans[i][j] = min_diff;
        }
      }
    }
    ans
  }
}