# Find the Grid of Region Average
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-grid-of-region-average)
Canonical: https://scaleengineer.com/dsa/problems/find-the-grid-of-region-average
**Data structures:** Array, Matrix
**Companies:** [jio](https://scaleengineer.com/companies/jio)
---
## Problem
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`.

**Example 1:**

**Input:** image = \[\[5,6,7,10\],\[8,9,10,10\],\[11,12,13,10\]\], threshold = 3

**Output:** \[\[9,9,9,9\],\[9,9,9,9\],\[9,9,9,9\]\]

**Explanation:**

![](https://assets.glich.co/dsa/find-the-grid-of-region-average/image0.png)

There are two regions as illustrated above. The average intensity of the first region is 9, while the average intensity of the second region is 9.67 which is rounded down to 9\. The average intensity of both of the regions is (9 + 9) / 2 = 9\. As all the pixels belong to either region 1, region 2, or both of them, the intensity of every pixel in the result is 9.

Please note that the rounded-down values are used when calculating the average of multiple regions, hence the calculation is done using 9 as the average intensity of region 2, not 9.67.

**Example 2:**

**Input:** image = \[\[10,20,30\],\[15,25,35\],\[20,30,40\],\[25,35,45\]\], threshold = 12

**Output:** \[\[25,25,25\],\[27,27,27\],\[27,27,27\],\[30,30,30\]\]

**Explanation:**

![](https://assets.glich.co/dsa/find-the-grid-of-region-average/image1.png)

There are two regions as illustrated above. The average intensity of the first region is 25, while the average intensity of the second region is 30\. The average intensity of both of the regions is (25 + 30) / 2 = 27.5 which is rounded down to 27.

All the pixels in row 0 of the image belong to region 1, hence all the pixels in row 0 in the result are 25\. Similarly, all the pixels in row 3 in the result are 30\. The pixels in rows 1 and 2 of the image belong to region 1 and region 2, hence their assigned value is 27 in the result.

**Example 3:**

**Input:** image = \[\[5,6,7\],\[8,9,10\],\[11,12,13\]\], threshold = 1

**Output:** \[\[5,6,7\],\[8,9,10\],\[11,12,13\]\]

**Explanation:**

There is only one `3 x 3` subgrid, while it does not have the condition on difference of adjacent pixels, for example, the difference between `image[0][0]` and `image[1][0]` is `|5 - 8| = 3 > threshold = 1`. None of them belong to any valid regions, so the `result` should be the same as `image`.

**Constraints:**

* `3 <= n, m <= 500`
* `0 <= image[i][j] <= 255`
* `0 <= threshold <= 255`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. It iterates through every possible `3x3` subgrid, checks if it qualifies as a "region" by examining all adjacent pixel pairs, and calculates its average if it does. After identifying all valid regions, it aggregates these averages for each pixel to compute the final result.
**Time:** O(m * n) - We iterate through all `(m-2)*(n-2)` potential region centers. For each, we do a constant amount of work (12 checks and 9 additions). Then, we iterate through the regions again to scatter the averages, which takes `O(m*n*9)`. Finally, we iterate through the grid once more. The total time is dominated by these `O(m*n)` operations. · **Space:** O(m * n) - We use several auxiliary grids: `regionAverages`, `sums`, and `counts`, each of size proportional to `m * n`.
**Pros:** Simple to understand and implement as it directly follows the problem's definition.; Does not require complex data structures.
**Cons:** Performs redundant calculations. For each `3x3` subgrid, it re-calculates the sum of 9 pixels and re-checks 12 adjacencies, even though adjacent subgrids share pixels and edges.
### Explanation
The brute-force method involves three main stages. First, we identify all valid `3x3` regions. A `3x3` region is centered at `(r, c)` where `1 <= r < m-1` and `1 <= c < n-1`. We iterate through all such possible centers. For each center, we perform 12 checks on adjacent pixel pairs within the `3x3` subgrid to see if their absolute intensity difference is within the `threshold`. If all checks pass, the subgrid is a valid region. We then calculate its average intensity by summing the 9 pixel values and dividing by 9. We store these averages in a 2D array. Second, after identifying all valid regions and their averages, we create two auxiliary grids: one to store the sum of averages for each pixel (`sums`) and another to count how many regions each pixel belongs to (`counts`). We iterate through our stored valid regions and for each one, we update the `sums` and `counts` for all 9 pixels within it. This is a "scatter" approach. Finally, we compute the `result` grid. For each pixel `(i, j)`, if `counts[i][j]` is zero, `result[i][j]` is `image[i][j]`. Otherwise, it's `sums[i][j] / counts[i][j]`.

```java
class Solution {
    public int[][] resultGrid(int[][] image, int threshold) {
        int m = image.length;
        int n = image[0].length;

        int[][] regionAverages = new int[m][n];

        // Step 1: Find all valid regions and calculate their averages
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                regionAverages[i][j] = calculateRegionAverage(image, i, j, threshold);
            }
        }

        // Step 2: Aggregate the averages for each pixel
        long[][] sums = new long[m][n];
        int[][] counts = new int[m][n];

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (regionAverages[i][j] != -1) {
                    // This is a valid region, scatter its average to its 9 pixels
                    for (int row = i - 1; row <= i + 1; row++) {
                        for (int col = j - 1; col <= j + 1; col++) {
                            sums[row][col] += regionAverages[i][j];
                            counts[row][col]++;
                        }
                    }
                }
            }
        }

        // Step 3: Calculate the final result grid
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (counts[i][j] == 0) {
                    result[i][j] = image[i][j];
                } else {
                    result[i][j] = (int) (sums[i][j] / counts[i][j]);
                }
            }
        }

        return result;
    }

    private int calculateRegionAverage(int[][] image, int r, int c, int threshold) {
        // Check horizontal differences in the 3x3 grid
        for (int i = r - 1; i <= r + 1; i++) {
            if (Math.abs(image[i][c - 1] - image[i][c]) > threshold ||
                Math.abs(image[i][c] - image[i][c + 1]) > threshold) {
                return -1;
            }
        }
        // Check vertical differences in the 3x3 grid
        for (int j = c - 1; j <= c + 1; j++) {
            if (Math.abs(image[r - 1][j] - image[r][j]) > threshold ||
                Math.abs(image[r][j] - image[r + 1][j]) > threshold) {
                return -1;
            }
        }
        
        // If valid, calculate sum
        int sum = 0;
        for (int i = r - 1; i <= r + 1; i++) {
            for (int j = c - 1; j <= c + 1; j++) {
                sum += image[i][j];
            }
        }
        return sum / 9;
    }
}
```
### Algorithm
- Get the dimensions `m` and `n` of the `image`.
- Create a 2D array `regionAverages` of size `m x n` to store the average of each valid region, centered at `(i, j)`. Initialize with a sentinel value like -1.
- Iterate through each possible center of a `3x3` subgrid, `(r, c)` from `(1, 1)` to `(m-2, n-2)`:
    - For each center, define a helper function `calculateRegionAverage`.
    - Inside the helper, check all 12 adjacent pixel pairs within the `3x3` subgrid. If any pair's absolute difference exceeds `threshold`, the region is invalid, so return -1.
    - If the region is valid, calculate the sum of its 9 pixels, compute the average (sum / 9), and return it.
    - Store the returned average in `regionAverages[r][c]`.
- Initialize two `m x n` grids, `sums` (using a `long` type to prevent overflow) and `counts`, to all zeros.
- Iterate through the `regionAverages` grid from `(1, 1)` to `(m-2, n-2)`. If `regionAverages[r][c]` is not -1:
    - This indicates a valid region. Iterate through its 9 pixels from `(r-1, c-1)` to `(r+1, c+1)`.
    - For each pixel `(i, j)` in the region, add the average to `sums[i][j]` and increment `counts[i][j]`.
- Initialize the final `m x n` `result` grid.
- Iterate through the `result` grid from `(0, 0)` to `(m-1, n-1)`:
    - If `counts[i][j]` is 0, it means the pixel belongs to no region. Set `result[i][j] = image[i][j]`.
    - Otherwise, set `result[i][j] = sums[i][j] / counts[i][j]`.
- Return the `result` grid.

## Optimized Approach with Prefix Sums
This approach improves upon the brute-force method by pre-calculating information that is used repeatedly. It uses a 2D prefix sum array (also known as a summed-area table) to calculate the sum of any `3x3` subgrid in constant time. It also pre-calculates the validity of differences between all adjacent pixels to speed up the region validation check, making the main loop more efficient.
**Time:** O(m * n) - The pre-computation steps for `prefixSum`, `hValid`, and `vValid` each take `O(m*n)`. The subsequent steps to find regions, aggregate averages, and compute the final result are also `O(m*n)`. The overall complexity remains `O(m*n)`, but it is faster in practice. · **Space:** O(m * n) - We use several auxiliary grids: `prefixSum`, `hValid`, `vValid`, `regionAverages`, `sums`, and `counts`, each of size proportional to `m * n`.
**Pros:** More efficient in practice than the brute-force approach due to a smaller constant factor on the time complexity.; Reduces the work inside the main loops from repeated calculations to fast, constant-time lookups.
**Cons:** Requires more auxiliary space for the pre-computed data structures (`prefixSum`, `hValid`, `vValid`).; The implementation is more complex due to the initial pre-computation phase.
### Explanation
The core idea is to avoid the redundant work done in the brute-force approach. We can optimize both the sum calculation and the validity check.

- **Optimized Sum Calculation:** We first build a 2D prefix sum array, `prefixSum`, over the `image` grid. `prefixSum[i+1][j+1]` stores the sum of all pixel intensities in the rectangle from `(0,0)` to `(i,j)`. This table can be built in `O(m*n)` time. With this table, the sum of any `3x3` region can be found in `O(1)` time with four lookups.

- **Optimized Validity Check:** We create two boolean grids, `hValid` and `vValid`. `hValid[i][j]` is true if `abs(image[i][j] - image[i][j+1]) <= threshold`, and `vValid[i][j]` is true if `abs(image[i][j] - image[i+1][j]) <= threshold`. These can also be computed in `O(m*n)` time.

With these pre-computed structures, the main loop to find valid regions becomes much faster. For each potential region center `(r, c)`, we perform 12 `O(1)` lookups in `hValid` and `vValid` to check for region validity, and one `O(1)` calculation using `prefixSum` to get the region sum. The rest of the algorithm, which involves aggregating the averages and calculating the final result, remains the same as the brute-force method.

```java
class Solution {
    public int[][] resultGrid(int[][] image, int threshold) {
        int m = image.length;
        int n = image[0].length;

        // Pre-computation Step
        long[][] prefixSum = new long[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = image[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
            }
        }

        boolean[][] hValid = new boolean[m][n - 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (Math.abs(image[i][j] - image[i][j + 1]) <= threshold) {
                    hValid[i][j] = true;
                }
            }
        }

        boolean[][] vValid = new boolean[m - 1][n];
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n; j++) {
                if (Math.abs(image[i][j] - image[i + 1][j]) <= threshold) {
                    vValid[i][j] = true;
                }
            }
        }

        // Step 1: Find valid regions and their averages
        int[][] regionAverages = new int[m][n];
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (isRegionValid(i, j, hValid, vValid)) {
                    long sum = prefixSum[i + 2][j + 2] - prefixSum[i - 1][j + 2] - prefixSum[i + 2][j - 1] + prefixSum[i - 1][j - 1];
                    regionAverages[i][j] = (int) (sum / 9);
                } else {
                    regionAverages[i][j] = -1;
                }
            }
        }

        // Step 2 & 3: Aggregate averages and compute final result
        long[][] sums = new long[m][n];
        int[][] counts = new int[m][n];

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (regionAverages[i][j] != -1) {
                    for (int row = i - 1; row <= i + 1; row++) {
                        for (int col = j - 1; col <= j + 1; col++) {
                            sums[row][col] += regionAverages[i][j];
                            counts[row][col]++;
                        }
                    }
                }
            }
        }

        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (counts[i][j] == 0) {
                    result[i][j] = image[i][j];
                } else {
                    result[i][j] = (int) (sums[i][j] / counts[i][j]);
                }
            }
        }

        return result;
    }

    private boolean isRegionValid(int r, int c, boolean[][] hValid, boolean[][] vValid) {
        for (int i = r - 1; i <= r + 1; i++) {
            if (!hValid[i][c - 1] || !hValid[i][c]) {
                return false;
            }
        }
        for (int j = c - 1; j <= c + 1; j++) {
            if (!vValid[r - 1][j] || !vValid[r][j]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Get dimensions `m`, `n`.
- **Pre-computation Step:**
    - Create and populate an `(m+1) x (n+1)` prefix sum grid `prefixSum` to allow for O(1) subgrid sum queries.
    - Create and populate an `m x (n-1)` boolean grid `hValid` where `hValid[i][j]` is true if `abs(image[i][j] - image[i][j+1]) <= threshold`.
    - Create and populate an `(m-1) x n` boolean grid `vValid` where `vValid[i][j]` is true if `abs(image[i][j] - image[i+1][j]) <= threshold`.
- Create a 2D array `regionAverages` of size `m x n` initialized to -1.
- Iterate `r` from `1` to `m-2` and `c` from `1` to `n-2`:
    - Check if the `3x3` region centered at `(r, c)` is valid by performing 12 lookups in the pre-computed `hValid` and `vValid` grids.
    - If valid, calculate the sum of the `3x3` region in `O(1)` using `prefixSum`. Compute the average and store it in `regionAverages[r][c]`.
- The remaining steps for aggregating averages and calculating the final result are identical to the brute-force approach:
    - Initialize `sums` and `counts` grids.
    - Scatter the valid `regionAverages` to the `sums` and `counts` grids.
    - Compute the final `result` grid based on `sums`, `counts`, and the original `image`.

# Solutions
### Java

```java
class Solution {
public
  int[][] resultGrid(int[][] image, int threshold) {
    int n = image.length;
    int m = image[0].length;
    int[][] ans = new int[n][m];
    int[][] ct = new int[n][m];
    for (int i = 0; i + 2 < n; ++i) {
      for (int j = 0; j + 2 < m; ++j) {
        boolean region = true;
        for (int k = 0; k < 3; ++k) {
          for (int l = 0; l < 2; ++l) {
            region &= Math.abs(image[i + k][j + l] - image[i + k][j + l + 1]) <=
                      threshold;
          }
        }
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 3; ++l) {
            region &= Math.abs(image[i + k][j + l] - image[i + k + 1][j + l]) <=
                      threshold;
          }
        }
        if (region) {
          int tot = 0;
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              tot += image[i + k][j + l];
            }
          }
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              ct[i + k][j + l]++;
              ans[i + k][j + l] += tot / 9;
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (ct[i][j] == 0) {
          ans[i][j] = image[i][j];
        } else {
          ans[i][j] /= ct[i][j];
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> resultGrid(vector<vector<int>> &image, int threshold) {
    int n = image.size(), m = image[0].size();
    vector<vector<int>> ans(n, vector<int>(m));
    vector<vector<int>> ct(n, vector<int>(m));
    for (int i = 0; i + 2 < n; ++i) {
      for (int j = 0; j + 2 < m; ++j) {
        bool region = true;
        for (int k = 0; k < 3; ++k) {
          for (int l = 0; l < 2; ++l) {
            region &=
                abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
          }
        }
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 3; ++l) {
            region &=
                abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
          }
        }
        if (region) {
          int tot = 0;
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              tot += image[i + k][j + l];
            }
          }
          for (int k = 0; k < 3; ++k) {
            for (int l = 0; l < 3; ++l) {
              ct[i + k][j + l]++;
              ans[i + k][j + l] += tot / 9;
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (ct[i][j] == 0) {
          ans[i][j] = image[i][j];
        } else {
          ans[i][j] /= ct[i][j];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]: n, m = len(image), len(image[0]) ans = [[0] * m for _ in range(n)] ct = [[0] * m for _ in range(n)] for i in range(n - 2): for j in range(m - 2): region = True for k in range(3): for l in range(2): region &= (abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold) for k in range(2): for l in range(3): region &= (abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold) if region: tot = 0 for k in range(3): for l in range(3): tot += image[i + k][j + l] for k in range(3): for l in range(3): ct[i + k][j + l] += 1 ans[i + k][j + l] += tot // 9 for i in range(n): for j in range(m): if ct[i][j] == 0: ans[i][j] = image[i][j] else: ans[i][j] //= ct[i][j] return ans

```