Python/Rust boring question with a simple solution
Intuition\n\nThe problem has a compex description with all those regions and adjacent values. Pixels are adjacent if they are up/down/left/right from one anothe
# Intuition\n\nThe problem has a compex description with all those regions and adjacent values. Pixels are adjacent if they are up/down/left/right from one another.\n\nWe define a function `is_region` (true if this y, x is a center of the region) which for one position (x)\n\n```\n . . .\n . x .\n . . .\n```\n\nchecks that for all adjacent values absolute difference is below the threshold. Now we check all the possible center of the regions and if it is a region we calculate the sum. Now we update both values:\n\n - sum array `S` with the sum\n - count array `C` with 1\n\nYou will need to do this for all 9 values in a region. The result for a value will be `S[y][x] // C[y][x]` if `C[y][x] != 0` otherwise it is original value in our image.\n\n# Complexity\n- Time complexity: $O(n \\cdot m)$\n- Space complexity: $O(n \\cdot m)$\n\n# Code\n```Rust []\nimpl Solution {\n\n  fn is_region(M: &Vec<Vec<i32>>, y: usize, x: usize, k: i32) -> bool {\n    return (M[y][x] - M[y - 1][x]).abs() <= k &&\n      (M[y][x] - M[y + 1][x]).abs() <= k &&\n      (M[y][x] - M[y][x - 1]).abs() <= k && \n      (M[y][x] - M[y][x + 1]).abs() <= k &&\n      (M[y - 1][x - 1] - M[y - 1][x]).abs() <= k &&\n      (M[y - 1][x - 1] - M[y][x - 1]).abs() <= k &&\n      (M[y - 1][x + 1] - M[y - 1][x]).abs() <= k &&\n      (M[y - 1][x + 1] - M[y][x + 1]).abs() <= k &&\n      (M[y + 1][x + 1] - M[y + 1][x]).abs() <= k &&\n      (M[y + 1][x + 1] - M[y][x + 1]).abs() <= k &&\n      (M[y + 1][x - 1] - M[y + 1][x]).abs() <= k && \n      (M[y + 1][x - 1] - M[y][x - 1]).abs() <= k\n  }\n\n  pub fn result_grid(mut M: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {\n    let (Y, X) = (M.len(), M[0].len());\n\n    let mut S = vec![vec![0; X]; Y];\n    let mut C = vec![vec![0; X]; Y];\n    \n    for y in 1 .. Y - 1 {\n      for x in 1 .. X - 1 {\n        if Self::is_region(&M, y, x, k) {\n          let s = (M[y - 1][x - 1] + M[y - 1][x] + M[y - 1][x + 1] + M[y][x - 1] + M[y][x] + M[y][x + 1] + M[y + 1][x - 1] + M[y + 1][x] + M[y + 1][x + 1]) / 9;\n          for i in -1 ..= 1 {\n            for j in -1 ..= 1 {\n              S[(y as i64 + i) as usize][(x as i64 + j) as usize] += s;\n              C[(y as i64 + i) as usize][(x as i64 + j) as usize] += 1;\n            }\n          }\n        }\n      }\n    }\n\n    for y in 0 .. Y {\n      for x in 0 .. X {\n        if C[y][x] > 0 {\n          M[y][x] = S[y][x] / C[y][x];\n        }\n      }\n    }\n\n    return M;\n  }\n}\n```\n```python []\nclass Solution:\n\n  def is_region(self, M, y, x, k):\n    if abs(M[y][x] - M[y - 1][x]) > k or abs(M[y][x] - M[y + 1][x]) > k or abs(M[y][x] - M[y][x - 1]) > k or abs(M[y][x] - M[y][x + 1]) > k:\n      return False\n\n    if abs(M[y - 1][x - 1] - M[y - 1][x]) > k or abs(M[y - 1][x - 1] - M[y][x - 1]) > k:\n      return False\n\n    if abs(M[y - 1][x + 1] - M[y - 1][x]) > k or abs(M[y - 1][x + 1] - M[y][x + 1]) > k:\n      return False\n\n    if abs(M[y + 1][x + 1] - M[y + 1][x]) > k or abs(M[y + 1][x + 1] - M[y][x + 1]) > k:\n      return False\n\n    if abs(M[y + 1][x - 1] - M[y + 1][x]) > k or abs(M[y + 1][x - 1] - M[y][x - 1]) > k:\n      return False\n\n    return True\n\n  def resultGrid(self, M: List[List[int]], k: int) -> List[List[int]]:\n    Y, X = len(M), len(M[0])\n    S = [[0] * X for _ in range(Y)]\n    C = [[0] * X for _ in range(Y)]\n\n    for y in range(1, Y - 1):\n      for x in range(1, X - 1):\n        if self.is_region(M, y, x, k):\n          s = sum(M[y - i][x - j] for i in range(-1, 2) for j in range(-1, 2)) // 9\n          for i in range(-1, 2):\n            for j in range(-1, 2):\n              S[y - i][x - j] += s\n              C[y - i][x - j] += 1\n\n    for y in range(Y):\n      for x in range(X):\n        if C[y][x] > 0:\n          M[y][x] = S[y][x] // C[y][x]\n\n    return M\n```\n\n---------------\n\nI feel like `is_region` can be rewritten with less number of checks, but didn\'t have time to look. If anyone has done it, please comment.
['Python', 'Rust']