Find the Grid of Region Average
MedPrompt
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:
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:
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 <= 5000 <= image[i][j] <= 2550 <= threshold <= 255
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Get the dimensions
mandnof theimage. - Create a 2D array
regionAveragesof sizem x nto 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
3x3subgrid,(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
3x3subgrid. If any pair's absolute difference exceedsthreshold, 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].
- For each center, define a helper function
- Initialize two
m x ngrids,sums(using alongtype to prevent overflow) andcounts, to all zeros. - Iterate through the
regionAveragesgrid from(1, 1)to(m-2, n-2). IfregionAverages[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 tosums[i][j]and incrementcounts[i][j].
- This indicates a valid region. Iterate through its 9 pixels from
- Initialize the final
m x nresultgrid. - Iterate through the
resultgrid from(0, 0)to(m-1, n-1):- If
counts[i][j]is 0, it means the pixel belongs to no region. Setresult[i][j] = image[i][j]. - Otherwise, set
result[i][j] = sums[i][j] / counts[i][j].
- If
- Return the
resultgrid.
Walkthrough
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].
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; }}Complexity
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`.
Trade-offs
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
3x3subgrid, it re-calculates the sum of 9 pixels and re-checks 12 adjacencies, even though adjacent subgrids share pixels and edges.
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.
Algorithm
- Get dimensions
m,n. - Pre-computation Step:
- Create and populate an
(m+1) x (n+1)prefix sum gridprefixSumto allow for O(1) subgrid sum queries. - Create and populate an
m x (n-1)boolean gridhValidwherehValid[i][j]is true ifabs(image[i][j] - image[i][j+1]) <= threshold. - Create and populate an
(m-1) x nboolean gridvValidwherevValid[i][j]is true ifabs(image[i][j] - image[i+1][j]) <= threshold.
- Create and populate an
- Create a 2D array
regionAveragesof sizem x ninitialized to -1. - Iterate
rfrom1tom-2andcfrom1ton-2:- Check if the
3x3region centered at(r, c)is valid by performing 12 lookups in the pre-computedhValidandvValidgrids. - If valid, calculate the sum of the
3x3region inO(1)usingprefixSum. Compute the average and store it inregionAverages[r][c].
- Check if the
- The remaining steps for aggregating averages and calculating the final result are identical to the brute-force approach:
- Initialize
sumsandcountsgrids. - Scatter the valid
regionAveragesto thesumsandcountsgrids. - Compute the final
resultgrid based onsums,counts, and the originalimage.
- Initialize
Walkthrough
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 theimagegrid.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 inO(m*n)time. With this table, the sum of any3x3region can be found inO(1)time with four lookups. -
Optimized Validity Check: We create two boolean grids,
hValidandvValid.hValid[i][j]is true ifabs(image[i][j] - image[i][j+1]) <= threshold, andvValid[i][j]is true ifabs(image[i][j] - image[i+1][j]) <= threshold. These can also be computed inO(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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.