Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 <= 255Problem summary: 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].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[5,6,7,10],[8,9,10,10],[11,12,13,10]] 3
[[10,20,30],[15,25,35],[20,30,40],[25,35,45]] 12
[[5,6,7],[8,9,10],[11,12,13]] 1
range-sum-query-2d-immutable)k-radius-subarray-averages)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3030: Find the Grid of Region Average
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;
}
}
// Accepted solution for LeetCode #3030: Find the Grid of Region Average
func resultGrid(image [][]int, threshold int) [][]int {
n := len(image)
m := len(image[0])
ans := make([][]int, n)
ct := make([][]int, n)
for i := range ans {
ans[i] = make([]int, m)
ct[i] = make([]int, m)
}
for i := 0; i+2 < n; i++ {
for j := 0; j+2 < m; j++ {
region := true
for k := 0; k < 3; k++ {
for l := 0; l < 2; l++ {
region = region && abs(image[i+k][j+l]-image[i+k][j+l+1]) <= threshold
}
}
for k := 0; k < 2; k++ {
for l := 0; l < 3; l++ {
region = region && abs(image[i+k][j+l]-image[i+k+1][j+l]) <= threshold
}
}
if region {
tot := 0
for k := 0; k < 3; k++ {
for l := 0; l < 3; l++ {
tot += image[i+k][j+l]
}
}
for k := 0; k < 3; k++ {
for l := 0; l < 3; l++ {
ct[i+k][j+l]++
ans[i+k][j+l] += tot / 9
}
}
}
}
}
for i := 0; i < n; i++ {
for 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
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
# Accepted solution for LeetCode #3030: Find the Grid of Region Average
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
// Accepted solution for LeetCode #3030: Find the Grid of Region Average
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3030: Find the Grid of Region Average
// 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;
// }
// }
// Accepted solution for LeetCode #3030: Find the Grid of Region Average
function resultGrid(image: number[][], threshold: number): number[][] {
const n: number = image.length;
const m: number = image[0].length;
const ans: number[][] = new Array(n).fill(0).map(() => new Array(m).fill(0));
const ct: number[][] = new Array(n).fill(0).map(() => new Array(m).fill(0));
for (let i = 0; i + 2 < n; ++i) {
for (let j = 0; j + 2 < m; ++j) {
let region: boolean = true;
for (let k = 0; k < 3; ++k) {
for (let l = 0; l < 2; ++l) {
region &&= Math.abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
}
}
for (let k = 0; k < 2; ++k) {
for (let l = 0; l < 3; ++l) {
region &&= Math.abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
}
}
if (region) {
let tot: number = 0;
for (let k = 0; k < 3; ++k) {
for (let l = 0; l < 3; ++l) {
tot += image[i + k][j + l];
}
}
for (let k = 0; k < 3; ++k) {
for (let l = 0; l < 3; ++l) {
ct[i + k][j + l]++;
ans[i + k][j + l] += Math.floor(tot / 9);
}
}
}
}
}
for (let i = 0; i < n; ++i) {
for (let j = 0; j < m; ++j) {
if (ct[i][j] === 0) {
ans[i][j] = image[i][j];
} else {
ans[i][j] = Math.floor(ans[i][j] / ct[i][j]);
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.