3272. Find the Grid of Region Average
My accepted Python solution to LeetCode problem 3272, Find the Grid of Region Average, running in 3469ms.
- Difficulty: Medium
- Python
- Runtime 3469ms
- Memory 38.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 3469ms, memory 38.7MB, accepted 2026-01-02.
class Solution:
def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
m, n = len(image), len(image[0])
# Check if a 3x3 region starting at (r, c) is valid
def is_valid_region(r, c):
for i in range(r, r + 3):
for j in range(c, c + 3):
# Check right neighbor
if j + 1 < c + 3:
if abs(image[i][j] - image[i][j+1]) > threshold:
return False
# Check bottom neighbor
if i + 1 < r + 3:
if abs(image[i][j] - image[i+1][j]) > threshold:
return False
return True
# Calculate average of 3x3 region
def region_avg(r, c):
total = 0
for i in range(r, r + 3):
for j in range(c, c + 3):
total += image[i][j]
return total // 9
# For each pixel, track sum of averages and count of regions it belongs to
sum_avg = [[0] * n for _ in range(m)]
count = [[0] * n for _ in range(m)]
# Check all possible 3x3 regions
for r in range(m - 2):
for c in range(n - 2):
if is_valid_region(r, c):
avg = region_avg(r, c)
for i in range(r, r + 3):
for j in range(c, c + 3):
sum_avg[i][j] += avg
count[i][j] += 1
# Build result
result = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if count[i][j] > 0:
result[i][j] = sum_avg[i][j] // count[i][j]
else:
result[i][j] = image[i][j]
return result