Skip to main content

Matrix

Find the Grid of Region Average Solution In C++/Python/java/JS

Problem Description:

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.
Illustration of Find the Grid of Region Average - Problem Description

Examples:

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:

Illustration of Find the Grid of Region Average - Example 1

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.

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:

Illustration of Find the Grid of Region Average - Example 2

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.

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 the image.

Constraints:

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

Problem Statement Breakdown

Imagine you're working with a digital photograph on your computer. This problem is asking us to create a special "smoothing" effect on that image. Let me explain everything in the simplest way possible!

What is a Digital Image?

Think of a digital image like a giant grid of tiny colored squares called pixels. Each pixel has a number that represents how bright or dark it is:

  • 0 = completely black
  • 255 = completely white
  • 128 = medium gray

So when we say image[i][j], we're talking about the brightness value of the pixel at row i and column j in our grid.

Understanding "Adjacent Pixels"

Imagine you're standing on one pixel - you can only move up, down, left, or right to reach an adjacent pixel. You cannot move diagonally!.

[X]
[X] [•] [X] ← The • is our current pixel where you're standing.
[X] ← X marks show adjacent pixels

What is a "Region"?

A region is like a small 3×3 neighbourhood in our image grid. Picture it like this:

[A] [B] [C]
[D] [E] [F] ← This entire 3×3 square is one region
[G] [H] [I]

But here's the catch: not every 3×3 square qualifies as a region!

The "Threshold" Rule :
For a 3×3 square to become a valid region, every pair of adjacent pixels in that square must have intensity values that are "close enough" to each other.

"Close enough" means: |pixel1_intensity - pixel2_intensity| ≤ threshold

Example:

If threshold = 10, then:

  • Pixel with intensity 50 and pixel with brightness 55 → Valid (difference = 5 ≤ 10)
  • Pixel with intensity 50 and pixel with brightness 65 → Invalid (difference = 15 > 10)

ALL adjacent pairs in the 3×3 square must satisfy this rule!

The Tricky Part: Multiple Region Membership

Here's where it gets interesting! A single pixel can belong to multiple regions at the same time.

Example:

Region 1: Region 2:
[A][B][C] [B][C][D]
[E][F][G] + [F][G][H] ← Pixels B, F, J, C, G, K belong to BOTH regions!
[I][J][K] [J][K][L]

If both regions are valid then pixels B, F, J, C, G, K belong to both the regions. while pixels A, E, I belong to only region 1 and pixels D H L belong to only region 2.

What We Need to Calculate

For each pixel in our image, we need to figure out its new intensity value using this process:

For all possible valid 3×3 regions (3×3 subgrid that follows the threshold rule). If the pixel belongs to at least one region, we need to:

  1. Calculate the average brightness of each region the pixel belongs to
  2. Round down each region's average.
  3. If a pixel belongs to multiple regions, Take the average of all those rounded down values and round down the resultant value again.
  4. If the pixel doesn't belong to any region, keep its original brightness value

Example:

Let's assume the grid looks like this:

[10] [20] [30] [35]
[40] [50] [60] [65]
[70] [80] [90] [95]

Let's say pixel P belongs to 2 regions:

Region 1 has pixels with values:

[10] [20] [30]
[40] [50] [60] ← P is at position (1,1) with value 50
[70] [80] [90]

Region 2 has pixels with values:

[20] [30] [35]
[50] [60] [65] ← P is at position (1,1) with value 50 (same pixel!)
[80] [90] [95]

Step-by-Step Calculation:

  1. Region 1 average = (10+20+30+40+50+60+70+80+90)/9 = 450/9 = 50
  2. Region 2 average = (20+30+35+50+60+65+80+90+95)/9 = 525/9 = 58.33..
  3. Round down each region's average:
    • Region 1 → floor(50) = 50
    • Region 2 → floor(58.33..) = 58
  4. Average of rounded values = (50+58)/2 = 54
  5. Round down final result = floor(52) = 54

So result_of_pixel_P = 54

Approach

Intuition:

At this point, we know what needs to be done. Let's just try to do exactly what the problem asks us to do. We will go with a brute force solution. Before getting to the approach, let's recap what we need to do:

  1. Find all valid 3×3 regions in the image grid
  2. Calculate the average intensity for each valid region
  3. Determine the final intensity for each pixel based on all regions it belongs to

So, first of all we need to find the valid regions from the grid. To do this in a brute force manner, we will go through all the 3×3 subgrids in the main grid and check for their validity.

How to identify a 3×3 subgrid?

Observation: A very obvious thing we can make use of here is that every 3×3 subgrid has only 1 centre cell. So that means we can use the centre position to identify a 3×3 subgrid. Any cell can act as a centre of a 3×3 subgrid if all the surrounding cell positions are within the grid bounds.

Example: In a 5×5 grid, the cell at position (2,2) can be the center of a 3×3 subgrid because all positions from (1,1) to (3,3) are valid. However, a cell at position (0,0) cannot be a center because positions like (-1,-1) would be out of bounds.

How do you check if a subgrid is valid?

Rule: The 3×3 subgrid is valid only when the absolute difference between any two adjacent cells within the subgrid is less than or equal to the threshold given in the input.

We know that the adjacent positions of any cell are at most 4: up, down, left, and right. So, to check if a subgrid is valid, we can go through each cell in the 3×3 region and check if the intensity difference between that cell and each of its adjacent cells (within the same 3×3 region) is less than or equal to the threshold. If any pair violates this condition, then we know that the subgrid is invalid, and we simply move on to check another subgrid.

Once we are done with this part, we can now shift towards calculation of our answer grid. The answer grid must store the final intensity value for each pixel, taking into account the average of all the valid regions that the pixel belongs to.

Example: If a pixel belongs to 2 valid regions with averages 10 and 14, then the final intensity for that pixel would be (10+14)/2 = 12.
Illustration of Find the Grid of Region Average - Multiple Region Membership

How to calculate the answer grid?

To calculate the answer grid, we need two things for each cell:

  1. The sum of the averages of all the valid 3×3 subgrids the cell is part of
  2. The count of how many valid subgrids the cell is part of

With these two pieces of information, we know the final answer is the average of the averages of all the subgrids a cell is part of, which is simply the first value divided by the second value.

To calculate this, we will keep a vector<vector<pair<int, int>>> res, which is a 2D vector containing pairs where:

  • The first part of the pair stores the sum of averages of all valid 3×3 grids the cell belongs to
  • The second part of the pair stores the count of how many valid subgrids the cell is part of

How to populate the 2D array of pairs (res)?

To populate 'res', we can perform an update operation for each valid 3×3 region, which will do these steps:

  1. Calculate the sum of all the intensity values in the current valid 3×3 grid
  2. Divide it by 9 to get the subgrid average (using integer division for rounding down)
  3. For all the 9 cells of the current valid 3×3 grid:
    • Add the grid average to the first part of the pair, indicating that these 9 cells are part of a valid 3×3 grid
    • Increment the count in the second element of the pair, indicating that we found one more valid subgrid for those 9 cells

Final Step

Now that we have the 'res' array populated, we can then perform 'pair.first / pair.second' for each pair in the 2D grid. This will give us the required answer for each cell.

Special case: If a cell doesn't belong to any valid region (i.e., pair.second == 0), then we keep its original intensity value unchanged.

This approach ensures that we correctly handle pixels that belong to multiple overlapping regions by averaging their region averages, and we maintain the original values for pixels that don't belong to any valid region.

0:00
/1:30

Animation of Find the Grid of Region Average - Approach

Dry run

Input: image = [
[5, 8, 12, 20],
[7, 6, 10, 18],
[9, 5, 11, 22]
]
threshold = 8
Ouptut: [
[8, 8, 8, 20],
[8, 8, 8, 18],
[8, 8, 8, 22]
]


Step 1: resultGrid() Method Initialization

n = 3
m = 4
res = [
[{0,0}, {0,0}, {0,0}, {0,0}],
[{0,0}, {0,0}, {0,0}, {0,0}],
[{0,0}, {0,0}, {0,0}, {0,0}]
]
ans = [
[5, 8, 12, 20],
[7, 6, 10, 18],
[9, 5, 11, 22]
]
Step 2: Main Loop - Finding Valid Regions

Loop bounds: i from 1 to 1 (n-2 = 1), j from 1 to 2 (m-2 = 2)
Iterations: (1,1) and (1,2)

Iteration 1: i=1, j=1

Step 3: checkValidity(image, 1, 1, 8)

3×3 region centered at (1,1):

[5] [8] [12] ← (0,0), (0,1), (0,2)
[7] [6] [10] ← (1,0), (1,1), (1,2)
[9] [5] [11] ← (2,0), (2,1), (2,2)

Detailed adjacency checking:

x=0, y=0 (position (0,0), value=5):

  • k=0: nx=0+0=0, ny=0+1=1 → (0,1) is within bounds → |image - image| = |8-5| = 3 ≤ 8 ✓
  • k=1: nx=0+0=0, ny=0-1=-1 → ny=-1 < j-1=0, outside bounds, skip
  • k=2: nx=0+1=1, ny=0+0=0 → (1,0) is within bounds → |image - image| = |7-5| = 2 ≤ 8 ✓
  • k=3: nx=0-1=-1, ny=0+0=0 → nx=-1 < i-1=0, outside bounds, skip

x=0, y=1 (position (0,1), value=8):

  • k=0: nx=0, ny=2 → (0,2) within bounds → |image - image| = |12-8| = 4 ≤ 8 ✓
  • k=1: nx=0, ny=0 → (0,0) within bounds → |image - image| = |5-8| = 3 ≤ 8 ✓
  • k=2: nx=1, ny=1 → (1,1) within bounds → |image - image| = |6-8| = 2 ≤ 8 ✓
  • k=3: nx=-1, ny=1 → outside bounds, skip

x=0, y=2 (position (0,2), value=12):

  • k=0: nx=0, ny=3 → ny=3 > j+1=2, outside bounds, skip
  • k=1: nx=0, ny=1 → (0,1) within bounds → |image - image| = |8-12| = 4 ≤ 8 ✓
  • k=2: nx=1, ny=2 → (1,2) within bounds → |image - image| = |10-12| = 2 ≤ 8 ✓
  • k=3: nx=-1, ny=2 → outside bounds, skip

x=1, y=0 (position (1,0), value=7):

  • k=0: nx=1, ny=1 → (1,1) within bounds → |image - image| = |6-7| = 1 ≤ 8 ✓
  • k=1: nx=1, ny=-1 → outside bounds, skip
  • k=2: nx=2, ny=0 → (2,0) within bounds → |image - image| = |9-7| = 2 ≤ 8 ✓
  • k=3: nx=0, ny=0 → (0,0) within bounds → |image - image| = |5-7| = 2 ≤ 8 ✓

x=1, y=1 (position (1,1), value=6):

  • k=0: nx=1, ny=2 → (1,2) within bounds → |image - image| = |10-6| = 4 ≤ 8 ✓
  • k=1: nx=1, ny=0 → (1,0) within bounds → |image - image| = |7-6| = 1 ≤ 8 ✓
  • k=2: nx=2, ny=1 → (2,1) within bounds → |image - image| = |5-6| = 1 ≤ 8 ✓
  • k=3: nx=0, ny=1 → (0,1) within bounds → |image - image| = |8-6| = 2 ≤ 8 ✓

x=1, y=2 (position (1,2), value=10):

  • k=0: nx=1, ny=3 → outside bounds, skip
  • k=1: nx=1, ny=1 → (1,1) within bounds → |image - image| = |6-10| = 4 ≤ 8 ✓
  • k=2: nx=2, ny=2 → (2,2) within bounds → |image - image| = |11-10| = 1 ≤ 8 ✓
  • k=3: nx=0, ny=2 → (0,2) within bounds → |image - image| = |12-10| = 2 ≤ 8 ✓

x=2, y=0 (position (2,0), value=9):

  • k=0: nx=2, ny=1 → (2,1) within bounds → |image - image| = |5-9| = 4 ≤ 8 ✓
  • k=1: nx=2, ny=-1 → outside bounds, skip
  • k=2: nx=3, ny=0 → outside bounds, skip
  • k=3: nx=1, ny=0 → (1,0) within bounds → |image - image| = |7-9| = 2 ≤ 8 ✓

x=2, y=1 (position (2,1), value=5):

  • k=0: nx=2, ny=2 → (2,2) within bounds → |image - image| = |11-5| = 6 ≤ 8 ✓
  • k=1: nx=2, ny=0 → (2,0) within bounds → |image - image| = |9-5| = 4 ≤ 8 ✓
  • k=2: nx=3, ny=1 → nx=3 > i+1=2, outside bounds, skip
  • k=3: nx=1, ny=1 → (1,1) within bounds → |image - image| = |6-5| = 1 ≤ 8 ✓

x=2, y=2 (position (2,2), value=11):

  • k=0: nx=2, ny=3 → ny=3 > j+1=2, outside bounds, skip
  • k=1: nx=2, ny=1 → (2,1) within bounds → |image - image| = |5-11| = 6 ≤ 8 ✓
  • k=2: nx=3, ny=2 → nx=3 > i+1=2, outside bounds, skip
  • k=3: nx=1, ny=2 → (1,2) within bounds → |image - image| = |10-11| = 1 ≤ 8 ✓

Result: valid = true (all adjacency checks now pass with threshold=8)

Step 4: update(res, image, 1, 1, 3, 4)

Calculate sum:

sum = 5 + 8 + 12 + 7 + 6 + 10 + 9 + 5 + 11 = 73
sum = sum/9 = 73/9 = 8 (integer division)

Update res array:

res[0][0] = {0+8, 0+1} = {8, 1}
res[0][1] = {0+8, 0+1} = {8, 1}
res[0][2] = {0+8, 0+1} = {8, 1}
res[1][0] = {0+8, 0+1} = {8, 1}
res[1][1] = {0+8, 0+1} = {8, 1}
res[1][2] = {0+8, 0+1} = {8, 1}
res[2][0] = {0+8, 0+1} = {8, 1}
res[2][1] = {0+8, 0+1} = {8, 1}
res[2][2] = {0+8, 0+1} = {8, 1}


Iteration 2: i=1, j=2

Step 5: checkValidity(image, 1, 2, 8)

3×3 region centered at (1,2):

[8] [12] [20] ← (0,1), (0,2), (0,3)
[6] [10] [18] ← (1,1), (1,2), (1,3)
[5] [11] [22] ← (2,1), (2,2), (2,3)

Key adjacency checks:

x=0, y=1 (position (0,1), value=8):

  • k=0: nx=0, ny=2 → |image - image| = |12-8| = 4 ≤ 8 ✓
  • k=1: nx=0, ny=0 → |image - image| = |5-8| = 3 ≤ 8 ✓
  • k=2: nx=1, ny=1 → |image - image| = |6-8| = 2 ≤ 8 ✓
  • k=3: nx=-1, ny=1 → outside bounds, skip

x=0, y=2 (position (0,2), value=12):

  • k=0: nx=0, ny=3 → |image - image| = |20-12| = 8 ≤ 8 ✓
  • k=1: nx=0, ny=1 → |image - image| = |8-12| = 4 ≤ 8 ✓
  • k=2: nx=1, ny=2 → |image - image| = |10-12| = 2 ≤ 8 ✓
  • k=3: nx=-1, ny=2 → outside bounds, skip

x=0, y=3 (position (0,3), value=20):

  • k=0: nx=0, ny=4 → outside bounds, skip
  • k=1: nx=0, ny=2 → |image - image| = |12-20| = 8 ≤ 8 ✓
  • k=2: nx=1, ny=3 → |image - image| = |18-20| = 2 ≤ 8 ✓
  • k=3: nx=-1, ny=3 → outside bounds, skip

x=1, y=0 (position (1,0), value=7):

  • k=0: nx=1, ny=1 → |image - image| = |6-7| = 1 ≤ 8 ✓
  • k=1: nx=1, ny=-1 → outside bounds, skip
  • k=2: nx=2, ny=0 → |image - image| = |9-7| = 2 ≤ 8 ✓
  • k=3: nx=0, ny=0 → |image - image| = |5-7| = 2 ≤ 8 ✓

x=1, y=1 (position (1,1), value=6):

  • k=0: nx=1, ny=2 → |image - image| = |10-6| = 4 ≤ 8 ✓
  • k=1: nx=1, ny=0 → |image - image| = |7-6| = 1 ≤ 8 ✓
  • k=2: nx=2, ny=1 → |image - image| = |5-6| = 1 ≤ 8 ✓
  • k=3: nx=0, ny=1 → |image - image| = |8-6| = 2 ≤ 8 ✓

x=1, y=2 (position (1,2), value=10):

  • k=0: nx=1, ny=3 → |image - image| = |18-10| = 8 ≤ 8 ✓
  • k=1: nx=1, ny=1 → |image - image| = |6-10| = 4 ≤ 8 ✓
  • k=2: nx=2, ny=2 → |image - image| = |11-10| = 1 ≤ 8 ✓
  • k=3: nx=0, ny=2 → |image - image| = |12-10| = 2 ≤ 8 ✓

x=2, y=1 (position (2,1), value=5):

  • k=0: nx=2, ny=2 → |image - image| = |11-5| = 6 ≤ 8 ✓
  • k=1: nx=2, ny=0 → |image - image| = |9-5| = 4 ≤ 8 ✓
  • k=2: nx=3, ny=1 → outside bounds, skip
  • k=3: nx=1, ny=1 → |image - image| = |6-5| = 1 ≤ 8 ✓

x=2, y=2 (position (2,2), value=11):

  • k=0: nx=2, ny=3 → |image - image| = |22-11| = 11 > 8 ✗
  • k=1: nx=2, ny=1 → |image - image| = |5-11| = 6 ≤ 8 ✓
  • k=2: nx=3, ny=2 → outside bounds, skip
  • k=3: nx=1, ny=2 → |image - image| = |10-11| = 1 ≤ 8 ✓

x=2, y=3 (position (2,3), value=22):

  • k=0: nx=2, ny=4 → outside bounds, skip
  • k=1: nx=2, ny=2 → |image - image| = |11-22| = 11 > 8 ✗
  • k=2: nx=3, ny=3 → outside bounds, skip
  • k=3: nx=1, ny=3 → |image - image| = |18-22| = 4 ≤ 8 ✓

Result: valid = false (still fails due to |22-11| = 11 > 8)

Step 6: Final Result Construction

Current res array after first region:

res = [
[{8,1}, {8,1}, {8,1}, {0,0}],
[{8,1}, {8,1}, {8,1}, {0,0}],
[{8,1}, {8,1}, {8,1}, {0,0}]
]

Calculate ans for each position:

Positions (0,0) to (2,2): res[i][j].second = 1 ≠ 0

  • ans = res.first / res.second = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8
  • ans = 8/1 = 8

Positions in column 3: res[i].second = 0

  • ans = original value = 20
  • ans = original value = 18
  • ans = original value = 22

Final Output: ans = [
[8, 8, 8, 20],
[8, 8, 8, 18],
[8, 8, 8, 22]
]

Summary:

  • One valid region found (left 3×3 subgrid) with average 8
  • The right column retained its original values as it doesn't belong to any valid region

Steps to write code

Step 1: Initialize Basic Variables and Data Structures

  • Extract the dimensions of the input image (number of rows and columns)
  • Create a 2D result tracking structure where each cell stores two values: sum of region averages and count of regions the pixel belongs to
  • Initialize the final answer grid as a copy of the original image
  • Set up direction arrays for checking adjacent pixels (up, down, left, right movements)

Step 2: Design the Region Validation Logic

  • Create a helper function that checks if a 3×3 region centered at a given position is valid
  • The function should iterate through all pixels in the 3×3 subgrid
  • For each pixel in the subgrid, check all its adjacent neighbors within the same subgrid
  • Verify that the absolute difference between adjacent pixel intensities doesn't exceed the threshold
  • Return false immediately if any adjacent pair violates the threshold condition

Step 3: Design the Region Update Logic

  • Create a helper function that processes a valid 3×3 region
  • Calculate the sum of all 9 pixel values in the region
  • Compute the average intensity by dividing the sum by 9 (using integer division for rounding down)
  • Update the tracking structure for all 9 pixels in the region by adding the computed average and incrementing their region count

Step 4: Implement the Main Processing Loop

  • Iterate through all possible 3×3 region centers (avoiding border positions where a complete 3×3 region cannot fit)
  • For each potential region center, call the validation function
  • If the region is valid, call the update function to process that region
  • Continue until all possible regions have been checked

Step 5: Calculate Final Results

  • Iterate through every pixel in the image
  • For pixels that belong to at least one region, calculate their final intensity by dividing the sum of region averages by the number of regions they belong to
  • For pixels that don't belong to any region, keep their original intensity values
  • Store the computed values in the final answer grid

Step 6: Handle Edge Cases and Return

  • Ensure proper handling of images smaller than 3×3 (where no regions can exist)
  • Verify that all boundary checks prevent array out-of-bounds access
  • Return the final processed image grid

Code for All Languages
C++ 
class Solution {
private:
    // Direction arrays for checking adjacent pixels (up, down, left, right)
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    
    // Function to check if a 3x3 region centered at (i,j) is valid
    bool checkValidity(vector<vector<int>>& image, int i, int j, int thr) {
        bool flag = true;
        
        // Iterate through all pixels in the 3x3 region
        for(int x = i-1; x <= i+1; ++x) {
            for(int y = j-1; y <= j+1; ++y) {
                
                // Check all 4 adjacent neighbors of current pixel
                for(int k = 0; k < 4; ++k) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    // Check if neighbor is within the 3x3 region bounds
                    if(nx >= i-1 && nx <= i+1 && ny >= j-1 && ny <= j+1) {
                        
                        // Check if intensity difference exceeds threshold
                        if(abs(image[nx][ny] - image[x][y]) > thr) {
                            return false;
                        }
                    }
                }
            }
        }
        return flag;
    }
    
    // Function to update result array for a valid 3x3 region
    void update(vector<vector<pair<int, int>>>& res, vector<vector<int>>& image, int i, int j, int n, int m) {
        int sum = 0;
        
        // Calculate sum of all pixels in the 3x3 region
        for(int x = i-1; x <= i+1; ++x) {
            for(int y = j-1; y <= j+1; ++y) {
                sum += image[x][y];
            }
        }
        
        // Calculate average (rounded down using integer division)
        sum /= 9;
        
        // Update all pixels in the region with this average
        for(int x = i-1; x <= i+1; ++x) {
            for(int y = j-1; y <= j+1; ++y) {
                // Add region average
                res[x][y].first += sum;
                // Increment region count
                res[x][y].second += 1;
            }
        }
    }
    
public:
    vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
        int n = image.size();
        int m = image[0].size();
        
        // Result tracking array: {sum_of_averages, count_of_regions}
        vector<vector<pair<int, int>>> res(n, vector<pair<int, int>>(m, {0, 0}));
        
        // Check all possible 3x3 region centers
        for(int i = 1; i < n-1; ++i) {
            for(int j = 1; j < m-1; ++j) {
                bool valid = checkValidity(image, i, j, threshold);
                if(valid) {
                    update(res, image, i, j, n, m);
                }
            }
        }
        
        // Initialize answer with original image
        vector<vector<int>> ans = image;
        
        // Calculate final result for each pixel
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(res[i][j].second != 0) {
                    // Pixel belongs to at least one region
                    ans[i][j] = res[i][j].first / res[i][j].second;
                }
                // If pixel doesn't belong to any region, keep original value
            }
        }
        
        return ans;
    }
};

Java 
class Solution {
    // Direction arrays for checking adjacent pixels (up, down, left, right)
    private int[] dx = {0, 0, 1, -1};
    private int[] dy = {1, -1, 0, 0};
    
    // Function to check if a 3x3 region centered at (i,j) is valid
    private boolean checkValidity(int[][] image, int i, int j, int thr) {
        
        // Iterate through all pixels in the 3x3 region
        for(int x = i-1; x <= i+1; x++) {
            for(int y = j-1; y <= j+1; y++) {
                
                // Check all 4 adjacent neighbors of current pixel
                for(int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    
                    // Check if neighbor is within the 3x3 region bounds
                    if(nx >= i-1 && nx <= i+1 && ny >= j-1 && ny <= j+1) {
                        
                        // Check if intensity difference exceeds threshold
                        if(Math.abs(image[nx][ny] - image[x][y]) > thr) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    
    // Function to update result array for a valid 3x3 region
    private void update(int[][][] res, int[][] image, int i, int j) {
        int sum = 0;
        
        // Calculate sum of all pixels in the 3x3 region
        for(int x = i-1; x <= i+1; x++) {
            for(int y = j-1; y <= j+1; y++) {
                sum += image[x][y];
            }
        }
        
        // Calculate average (rounded down using integer division)
        sum /= 9;
        
        // Update all pixels in the region with this average
        for(int x = i-1; x <= i+1; x++) {
            for(int y = j-1; y <= j+1; y++) {
                // Add region average
                res[x][y][0] += sum;
                // Increment region count
                res[x][y][1] += 1;
            }
        }
    }
    
    public int[][] resultGrid(int[][] image, int threshold) {
        int n = image.length;
        int m = image[0].length;
        
        // Result tracking array: [sum_of_averages, count_of_regions]
        int[][][] res = new int[n][m][2];
        
        // Check all possible 3x3 region centers
        for(int i = 1; i < n-1; i++) {
            for(int j = 1; j < m-1; j++) {
                boolean valid = checkValidity(image, i, j, threshold);
                if(valid) {
                    update(res, image, i, j);
                }
            }
        }
        
        // Initialize answer with original image
        int[][] ans = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                ans[i][j] = image[i][j];
            }
        }
        
        // Calculate final result for each pixel
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(res[i][j][1] != 0) {
                    // Pixel belongs to at least one region
                    ans[i][j] = res[i][j][0] / res[i][j][1];
                }
                // If pixel doesn't belong to any region, keep original value
            }
        }
        
        return ans;
    }
}

Python 
class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        # Direction arrays for checking adjacent pixels (up, down, left, right)
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        
        # Function to check if a 3x3 region centered at (i,j) is valid
        def checkValidity(i, j):
            
            # Iterate through all pixels in the 3x3 region
            for x in range(i-1, i+2):
                for y in range(j-1, j+2):
                    
                    # Check all 4 adjacent neighbors of current pixel
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        
                        # Check if neighbor is within the 3x3 region bounds
                        if i-1 <= nx <= i+1 and j-1 <= ny <= j+1:
                            
                            # Check if intensity difference exceeds threshold
                            if abs(image[nx][ny] - image[x][y]) > threshold:
                                return False
            return True
        
        # Function to update result array for a valid 3x3 region
        def update(i, j):
            sum_val = 0
            
            # Calculate sum of all pixels in the 3x3 region
            for x in range(i-1, i+2):
                for y in range(j-1, j+2):
                    sum_val += image[x][y]
            
            # Calculate average (rounded down using integer division)
            sum_val //= 9
            
            # Update all pixels in the region with this average
            for x in range(i-1, i+2):
                for y in range(j-1, j+2):
                    # Add region average
                    res[x][y][0] += sum_val
                    # Increment region count
                    res[x][y][1] += 1
        
        n = len(image)
        m = len(image[0])
        
        # Result tracking array: [sum_of_averages, count_of_regions]
        res = [[[0, 0] for _ in range(m)] for _ in range(n)]
        
        # Check all possible 3x3 region centers
        for i in range(1, n-1):
            for j in range(1, m-1):
                if checkValidity(i, j):
                    update(i, j)
        
        # Initialize answer with original image
        ans = [row[:] for row in image]
        
        # Calculate final result for each pixel
        for i in range(n):
            for j in range(m):
                if res[i][j][1] != 0:
                    # Pixel belongs to at least one region
                    ans[i][j] = res[i][j][0] // res[i][j][1]
                # If pixel doesn't belong to any region, keep original value
        
        return ans

Javascript 
/**
 * @param {number[][]} image
 * @param {number} threshold
 * @return {number[][]}
 */
var resultGrid = function(image, threshold) {
    // Direction arrays for checking adjacent pixels (up, down, left, right)
    const dx = [0, 0, 1, -1];
    const dy = [1, -1, 0, 0];
    
    // Function to check if a 3x3 region centered at (i,j) is valid
    function checkValidity(i, j) {
        
        // Iterate through all pixels in the 3x3 region
        for(let x = i-1; x <= i+1; x++) {
            for(let y = j-1; y <= j+1; y++) {
                
                // Check all 4 adjacent neighbors of current pixel
                for(let k = 0; k < 4; k++) {
                    const nx = x + dx[k];
                    const ny = y + dy[k];
                    
                    // Check if neighbor is within the 3x3 region bounds
                    if(nx >= i-1 && nx <= i+1 && ny >= j-1 && ny <= j+1) {
                        
                        // Check if intensity difference exceeds threshold
                        if(Math.abs(image[nx][ny] - image[x][y]) > threshold) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    
    // Function to update result array for a valid 3x3 region
    function update(i, j) {
        let sum = 0;
        
        // Calculate sum of all pixels in the 3x3 region
        for(let x = i-1; x <= i+1; x++) {
            for(let y = j-1; y <= j+1; y++) {
                sum += image[x][y];
            }
        }
        
        // Calculate average (rounded down using integer division)
        sum = Math.floor(sum / 9);
        
        // Update all pixels in the region with this average
        for(let x = i-1; x <= i+1; x++) {
            for(let y = j-1; y <= j+1; y++) {
                // Add region average
                res[x][y][0] += sum;
                // Increment region count
                res[x][y][1] += 1;
            }
        }
    }
    
    const n = image.length;
    const m = image[0].length;
    
    // Result tracking array: [sum_of_averages, count_of_regions]
    const res = Array(n).fill().map(() => Array(m).fill().map(() => [0, 0]));
    
    // Check all possible 3x3 region centers
    for(let i = 1; i < n-1; i++) {
        for(let j = 1; j < m-1; j++) {
            if(checkValidity(i, j)) {
                update(i, j);
            }
        }
    }
    
    // Initialize answer with original image
    const ans = image.map(row => [...row]);
    
    // Calculate final result for each pixel
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < m; j++) {
            if(res[i][j][1] !== 0) {
                // Pixel belongs to at least one region
                ans[i][j] = Math.floor(res[i][j][0] / res[i][j][1]);
            }
            // If pixel doesn't belong to any region, keep original value
        }
    }
    
    return ans;
};

Time Complexity: O(n × m)

Main Algorithm Steps with time complexity:

Step 1: Region Validation

  • What we do: For each possible 3×3 region, check if all adjacent pixel pairs satisfy the threshold condition
  • How many regions: (n-2) × (m-2) regions to check
  • Work per region: Check all adjacent pairs in a 3×3 grid
    • Each 3×3 grid has 9 pixels
    • Each pixel has up to 4 adjacent neighbors
    • Total adjacency checks per region = constant (always the same regardless of grid size)
  • Time for this step: O(n × m) × O(1) = O(n × m)

Step 2: Region Processing

  • What we do: For each valid region, calculate its average and update all 9 pixels in that region
  • Work per valid region:
    • Calculate sum of 9 pixels = O(1)
    • Update 9 pixels with region information = O(1)
  • Worst case: All regions are valid, so we process (n-2) × (m-2) regions
  • Time for this step: O(n × m) × O(1) = O(n × m)

Step 3: Final Result Calculation

  • What we do: For each pixel, calculate its final intensity based on all regions it belongs to
  • Work per pixel: Average the region averages and round down = O(1)
  • Total pixels: n × m
  • Time for this step: O(n × m)

Overall Time Complexity:

O(n × m) + O(n × m) + O(n × m) = O(n × m)

Key Insight:

The algorithm is linear in the size of the input grid because:

  • We visit each possible region center once
  • Each region operation takes constant time (3×3 is always 9 pixels)
  • Final processing visits each pixel once

This is optimal since we must examine every pixel at least once to produce the result.

Space Complexity : O(n × m)

Auxiliary Space Complexity:
It refers to the space Excluding Input and Output space used to solve the problem.

Main Data Structures Used:

1. Region Tracking Array (res):

  • Purpose: Store region information for each pixel
  • Structure: 2D array of pairs (sum_of_averages, count_of_regions)
  • Size: n × m pairs
  • Space: O(n × m)

2. Direction Arrays (dx, dy):

  • Purpose: Store movement directions for adjacency checking
  • Size: 4 elements each
  • Space: O(1)

3. Loop Variables and Temporary Variables:

  • Variables: i, j, x, y, k, nx, ny, sum, flag, valid
  • Space: O(1)

4. Function Call Stack:

  • Depth: Constant (no recursion, only function calls)
  • Space: O(1)

Auxiliary Space Complexity: O(n × m)

The dominant auxiliary space is the res array that tracks region membership and averages for each pixel.

Total Space Complexity:
It includes overall space complexity which is input plus output plus auxiliary space complexity.

Input Space:

  • Original image: n × m integers = O(n × m)

Output Space:

  • ans grid: n × m integers = O(n × m)

Auxiliary Space:

  • Region tracking and other variables: O(n × m)

Total Space Complexity: O(n × m)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems:-

1. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, handle multiple queries of the following type:

  • Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

  • NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

You must design an algorithm where sumRegion works on O(1) time complexity.

2. K Radius Subarray Averages

You are given a 0-indexed array nums of n integers, and an integer k.

The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.

Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.

The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.

  • For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.