LeetCode 3030 - Find the Grid of Region Average

The problem gives us a grayscale image represented as an m x n matrix called image. Every value in the matrix is an integer between 0 and 255, representing the intensity of a pixel. We must examine every possible 3 x 3 subgrid inside the image.

leetcodemediumarraymatrix

LeetCode Problem 3030

Difficulty: 🟡 Medium
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us a grayscale image represented as an m x n matrix called image. Every value in the matrix is an integer between 0 and 255, representing the intensity of a pixel.

We must examine every possible 3 x 3 subgrid inside the image. A 3 x 3 subgrid is considered a valid region if every pair of adjacent cells inside that subgrid differs by at most threshold.

Adjacency here means sharing an edge, not a corner. Therefore, inside each 3 x 3 block we only need to check horizontal and vertical neighbors.

If a 3 x 3 block is valid:

  1. Compute the average of its 9 cells.
  2. Round that average down using integer division.
  3. Every cell belonging to this region receives that region average as a contribution.

A single pixel may belong to multiple valid regions because different 3 x 3 windows can overlap.

For every cell:

  • If it belongs to one or more valid regions, its final value becomes the average of all contributing region averages, rounded down.
  • If it belongs to no valid region, its value stays unchanged from the original image.

The constraints are important:

  • m, n <= 500
  • Total cells can be as large as 250,000

This means we must avoid expensive repeated computations. A solution with very high polynomial complexity would time out.

The important edge cases include:

  • No valid regions at all, every cell remains unchanged.
  • Every possible 3 x 3 window is valid, many overlapping contributions occur.
  • Very small thresholds like 0, where only perfectly equal adjacent pixels can form a region.
  • Large thresholds like 255, where nearly every 3 x 3 window becomes valid.
  • Border cells that may belong to fewer regions than inner cells.

Approaches

Brute Force Approach

The brute force idea is straightforward:

  1. Enumerate every possible 3 x 3 subgrid.
  2. For each subgrid:
  • Check all adjacent pairs.
  • If valid, compute its average.
  1. For every valid region:
  • Visit all 9 cells again and append the region average into a list for that cell.
  1. Finally:

  • For every cell:

  • If its list is empty, keep original value.

  • Otherwise compute the average of all stored region averages.

This approach is correct because it directly follows the problem definition.

However, storing lists of contributions for every cell is inefficient in both time and memory. Also, repeatedly managing dynamic lists creates unnecessary overhead.

Key Insight for the Optimal Solution

The important observation is that we do not actually need to store every contribution individually.

For each cell we only need:

  • The sum of all contributing region averages
  • The number of contributing regions

Then the final value is simply:

sum // count

This transforms the problem into an accumulation process.

Another key observation is that a 3 x 3 region contains only 12 adjacency checks:

  • 6 horizontal edges
  • 6 vertical edges

Since the region size is fixed, validating one region takes constant time.

The total number of possible 3 x 3 windows is:

(m - 2) * (n - 2)

So the entire algorithm becomes linear in the number of cells.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n * k) Stores explicit contribution lists
Optimal O(m * n) O(m * n) Uses running sums and counts

Here, k represents the number of overlapping regions per cell.

Algorithm Walkthrough

  1. Create two auxiliary matrices:
  • region_sum[i][j], stores the total of all contributing region averages
  • region_count[i][j], stores how many valid regions include the cell
  1. Iterate through every possible top-left corner of a 3 x 3 window.

  • The top-left corner ranges from:

  • rows 0 to m - 3

  • columns 0 to n - 3

  1. For each 3 x 3 window, validate whether it forms a region.
  • Check every horizontal adjacent pair.
  • Check every vertical adjacent pair.
  • If any absolute difference exceeds threshold, the region is invalid.
  1. If the region is valid:
  • Compute the sum of all 9 cells.
  • Compute the rounded-down average:
average = total // 9
  1. Add this region contribution to all 9 cells inside the region.
  • Increment:
region_sum[r][c] += average
region_count[r][c] += 1
  1. After processing all regions, build the final result matrix.

  • For each cell:

  • If region_count[i][j] == 0, use original image value.

  • Otherwise:

result[i][j] = region_sum[i][j] // region_count[i][j]

Why it works

The algorithm works because every valid 3 x 3 region contributes exactly one rounded-down region average to each of its 9 cells. By accumulating the total contribution sum and contribution count separately, we preserve all information needed to compute the final rounded-down average for each cell. Since every region is checked exactly once and every valid contribution is added exactly once, the final matrix exactly matches the problem definition.

Python Solution

from typing import List

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        rows = len(image)
        cols = len(image[0])

        region_sum = [[0] * cols for _ in range(rows)]
        region_count = [[0] * cols for _ in range(rows)]

        for top in range(rows - 2):
            for left in range(cols - 2):

                valid = True

                # Check horizontal adjacent differences
                for r in range(top, top + 3):
                    for c in range(left, left + 2):
                        if abs(image[r][c] - image[r][c + 1]) > threshold:
                            valid = False
                            break
                    if not valid:
                        break

                # Check vertical adjacent differences
                if valid:
                    for r in range(top, top + 2):
                        for c in range(left, left + 3):
                            if abs(image[r][c] - image[r + 1][c]) > threshold:
                                valid = False
                                break
                        if not valid:
                            break

                if not valid:
                    continue

                total = 0

                for r in range(top, top + 3):
                    for c in range(left, left + 3):
                        total += image[r][c]

                average = total // 9

                for r in range(top, top + 3):
                    for c in range(left, left + 3):
                        region_sum[r][c] += average
                        region_count[r][c] += 1

        result = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                if region_count[r][c] == 0:
                    result[r][c] = image[r][c]
                else:
                    result[r][c] = (
                        region_sum[r][c] // region_count[r][c]
                    )

        return result

The implementation closely follows the algorithm.

The first section initializes two matrices that track contribution totals and contribution counts. These matrices allow us to avoid storing individual lists of region averages.

The nested loops over top and left enumerate every possible 3 x 3 subgrid.

The validation phase checks horizontal and vertical neighboring cells separately. Early exits are used whenever an invalid adjacent pair is found, avoiding unnecessary work.

Once a region is confirmed valid, the code computes the region average using integer division. That average is then added to every cell inside the 3 x 3 block.

Finally, the result matrix is constructed. Cells with no contributions retain their original values, while cells with one or more contributions compute the rounded-down average of all region averages.

Go Solution

func resultGrid(image [][]int, threshold int) [][]int {
	rows := len(image)
	cols := len(image[0])

	regionSum := make([][]int, rows)
	regionCount := make([][]int, rows)

	for i := 0; i < rows; i++ {
		regionSum[i] = make([]int, cols)
		regionCount[i] = make([]int, cols)
	}

	for top := 0; top < rows-2; top++ {
		for left := 0; left < cols-2; left++ {

			valid := true

			// Horizontal checks
			for r := top; r < top+3 && valid; r++ {
				for c := left; c < left+2; c++ {
					diff := image[r][c] - image[r][c+1]
					if diff < 0 {
						diff = -diff
					}

					if diff > threshold {
						valid = false
						break
					}
				}
			}

			// Vertical checks
			for r := top; r < top+2 && valid; r++ {
				for c := left; c < left+3; c++ {
					diff := image[r][c] - image[r+1][c]
					if diff < 0 {
						diff = -diff
					}

					if diff > threshold {
						valid = false
						break
					}
				}
			}

			if !valid {
				continue
			}

			total := 0

			for r := top; r < top+3; r++ {
				for c := left; c < left+3; c++ {
					total += image[r][c]
				}
			}

			average := total / 9

			for r := top; r < top+3; r++ {
				for c := left; c < left+3; c++ {
					regionSum[r][c] += average
					regionCount[r][c]++
				}
			}
		}
	}

	result := make([][]int, rows)

	for r := 0; r < rows; r++ {
		result[r] = make([]int, cols)

		for c := 0; c < cols; c++ {
			if regionCount[r][c] == 0 {
				result[r][c] = image[r][c]
			} else {
				result[r][c] = regionSum[r][c] / regionCount[r][c]
			}
		}
	}

	return result
}

The Go implementation mirrors the Python logic very closely.

Since Go does not provide a built-in absolute value function for integers without importing packages, the code computes absolute differences manually.

All matrices are initialized explicitly using nested make calls. Integer division in Go already performs floor division for positive numbers, which matches the problem requirements.

No special nil handling is required because the constraints guarantee valid input dimensions.

Worked Examples

Example 1

image =
[
    [5, 6, 7, 10],
    [8, 9, 10, 10],
    [11, 12, 13, 10]
]

threshold = 3

Possible 3 x 3 windows:

Top-left Window
(0,0) columns 0-2
(0,1) columns 1-3

Window 1, top-left (0,0)

Subgrid:

5   6   7
8   9  10
11 12 13

All adjacent differences are at most 3.

Region sum:

5+6+7+8+9+10+11+12+13 = 81

Region average:

81 // 9 = 9

All 9 cells receive contribution 9.

Window 2, top-left (0,1)

Subgrid:

6   7  10
9  10  10
12 13  10

All adjacent differences are at most 3.

Region sum:

6+7+10+9+10+10+12+13+10 = 87

Region average:

87 // 9 = 9

Now overlapping cells receive another contribution of 9.

Final averages become 9 everywhere.

Output:

[
    [9,9,9,9],
    [9,9,9,9],
    [9,9,9,9]
]

Example 2

image =
[
    [10,20,30],
    [15,25,35],
    [20,30,40],
    [25,35,45]
]

There are two possible 3 x 3 windows.

First region

10 20 30
15 25 35
20 30 40

Sum:

225

Average:

25

Second region

15 25 35
20 30 40
25 35 45

Sum:

270

Average:

30

Rows 1 and 2 belong to both regions.

Combined value:

(25 + 30) // 2 = 27

Final result:

[
    [25,25,25],
    [27,27,27],
    [27,27,27],
    [30,30,30]
]

Example 3

image =
[
    [5,6,7],
    [8,9,10],
    [11,12,13]
]

threshold = 1

Only one 3 x 3 window exists.

Check vertical adjacency:

|5 - 8| = 3

This exceeds the threshold.

Therefore no valid region exists.

All cells keep original values.

Output:

[
    [5,6,7],
    [8,9,10],
    [11,12,13]
]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each 3 x 3 region requires constant work
Space O(m * n) Two auxiliary matrices are stored

The total number of 3 x 3 windows is (m - 2) * (n - 2). Since each window performs only a fixed number of operations, validation and accumulation both take constant time per window. Therefore the total runtime is linear in the number of cells.

The extra memory comes from the region_sum and region_count matrices.

Test Cases

from typing import List

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        rows = len(image)
        cols = len(image[0])

        region_sum = [[0] * cols for _ in range(rows)]
        region_count = [[0] * cols for _ in range(rows)]

        for top in range(rows - 2):
            for left in range(cols - 2):

                valid = True

                for r in range(top, top + 3):
                    for c in range(left, left + 2):
                        if abs(image[r][c] - image[r][c + 1]) > threshold:
                            valid = False
                            break
                    if not valid:
                        break

                if valid:
                    for r in range(top, top + 2):
                        for c in range(left, left + 3):
                            if abs(image[r][c] - image[r + 1][c]) > threshold:
                                valid = False
                                break
                        if not valid:
                            break

                if not valid:
                    continue

                total = 0

                for r in range(top, top + 3):
                    for c in range(left, left + 3):
                        total += image[r][c]

                avg = total // 9

                for r in range(top, top + 3):
                    for c in range(left, left + 3):
                        region_sum[r][c] += avg
                        region_count[r][c] += 1

        result = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                if region_count[r][c] == 0:
                    result[r][c] = image[r][c]
                else:
                    result[r][c] = (
                        region_sum[r][c] // region_count[r][c]
                    )

        return result

sol = Solution()

# Example 1
assert sol.resultGrid(
    [[5,6,7,10],[8,9,10,10],[11,12,13,10]],
    3
) == [
    [9,9,9,9],
    [9,9,9,9],
    [9,9,9,9]
]  # overlapping valid regions

# Example 2
assert sol.resultGrid(
    [[10,20,30],[15,25,35],[20,30,40],[25,35,45]],
    12
) == [
    [25,25,25],
    [27,27,27],
    [27,27,27],
    [30,30,30]
]  # two stacked valid regions

# Example 3
assert sol.resultGrid(
    [[5,6,7],[8,9,10],[11,12,13]],
    1
) == [
    [5,6,7],
    [8,9,10],
    [11,12,13]
]  # no valid region

# Minimum size valid region
assert sol.resultGrid(
    [[1,1,1],[1,1,1],[1,1,1]],
    0
) == [
    [1,1,1],
    [1,1,1],
    [1,1,1]
]  # exactly one valid region

# Large threshold makes all regions valid
assert sol.resultGrid(
    [[1,100,1],[100,1,100],[1,100,1]],
    255
) == [
    [45,45,45],
    [45,45,45],
    [45,45,45]
]  # all differences allowed

# Single invalid edge ruins region
assert sol.resultGrid(
    [[1,1,1],[1,100,1],[1,1,1]],
    10
) == [
    [1,1,1],
    [1,100,1],
    [1,1,1]
]  # center creates invalid adjacency

# Multiple overlapping regions
assert sol.resultGrid(
    [
        [10,10,10,10],
        [10,10,10,10],
        [10,10,10,10],
        [10,10,10,10]
    ],
    0
) == [
    [10,10,10,10],
    [10,10,10,10],
    [10,10,10,10],
    [10,10,10,10]
]  # every 3x3 window valid
Test Why
Example 1 Verifies overlapping horizontal regions
Example 2 Verifies vertically overlapping regions
Example 3 Verifies behavior when no region is valid
Uniform 3x3 grid Tests smallest valid configuration
Threshold 255 Tests maximum threshold behavior
Invalid center spike Ensures one bad edge invalidates region
Fully uniform 4x4 grid Tests many overlapping valid regions

Edge Cases

No Valid Regions

A common bug is incorrectly modifying cells even when no valid 3 x 3 region exists. In this situation every region_count[i][j] remains zero. The implementation explicitly checks for this and copies the original pixel value into the result.

Multiple Overlapping Regions

A pixel may belong to several valid regions simultaneously. Incorrect solutions sometimes overwrite values instead of accumulating them. This implementation uses separate sum and count matrices so every contribution is preserved correctly before the final averaging step.

Threshold Equal to Zero

When threshold = 0, every adjacent pair inside a valid region must have identical values. This can easily expose bugs in adjacency checking logic. The implementation checks all horizontal and vertical neighbor pairs independently, ensuring strict equality is enforced correctly.