Find the grid of region average

Array Matrix

43.3% acceptance

Feb 25, 2026

134

You are given m x n grid image which represents a grayscale image, where image[i][j] represents a pixel with intensity in the range [0..255]. You are also given a non-negative integer threshold. Two pixels are adjacent if they share an edge. A region is a 3 x 3 subgrid where the absolute difference in intensity between any two adjacent pixels is less than or equal to threshold. All pixels in a region belong to that region, note that a pixel can belong to multiple regions. You need to calculate a m x n grid result, where result[i][j] is the average intensity of the regions to which image[i][j] belongs, rounded down to the nearest integer. If image[i][j] belongs to multiple regions, result[i][j] is the average of the rounded-down average intensities of these regions, rounded down to the nearest integer. If image[i][j] does not belong to any region, result[i][j] is equal to image[i][j]. Return the grid result.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn result_grid(image: Vec<Vec<i32>>, threshold: i32) -> Vec<Vec<i32>> {
    let m = image.len();
    let n = image[0].len();
    let mut sum_grid = vec![vec![0i64; n]; m];
    let mut cnt_grid = vec![vec![0i64; n]; m];
    for r in 0..m.saturating_sub(2) {
      'outer: for c in 0..n.saturating_sub(2) {
        // Check if 3x3 region starting at (r,c) is valid
        for i in r..r+3 {
          for j in c..c+3 {
            if j+1 < c+3 && (image[i][j] - image[i][j+1]).abs() > threshold { continue 'outer; }
            if i+1 < r+3 && (image[i][j] - image[i+1][j]).abs() > threshold { continue 'outer; }
          }
        }
        // Valid region
        let mut s = 0i32;
        for i in r..r+3 { for j in c..c+3 { s += image[i][j]; } }
        let avg = s / 9;
        for i in r..r+3 { for j in c..c+3 {
          sum_grid[i][j] += avg as i64;
          cnt_grid[i][j] += 1;
        }}
      }
    }
    let mut res = image.clone();
    for i in 0..m {
      for j in 0..n {
        if cnt_grid[i][j] > 0 {
          res[i][j] = (sum_grid[i][j] / cnt_grid[i][j]) as i32;
        }
      }
    }
    res
  }
}