Find the Grid of Region Average solution and explanation
4 more videos on this problem
3030. Find the Grid of Region Average | Array | Matrix | Weekly Contest 383Aryan Mittal · 26:21 · 1K views
3030 Find the Grid of Region Average || Implement the requirements given in the question ✅Ayush Rao · 11:53 · 715 views
3030. Find the Grid of Region Average (Leetcode Medium)Programming Live with Larry · 17:13 · 356 views
Leetcode Weekly 383 | Leetcode 3030 Find the Grid of Region Average | Coding with BharatBharat Khanna · 30:45 · 301 views
Leetcode 3030. Find the Grid of Region AverageAlgorithms Casts · 13:32 · 203 views
The problem
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
Approach overview
Problem Overview: You receive an m x n image grid and a threshold. For every possible 3 x 3 region, check whether all adjacent cells inside the region differ by at most the threshold. If the region is valid, compute the floor of the average of its 9 values and contribute that value to every cell in the region. A cell may belong to multiple valid regions, so the final grid value becomes the average of all region averages covering that cell. If no valid region covers a cell, keep the original value.
Approach 1: Brute-Force Region Detection (O(m*n) time, O(m*n) space)
Iterate through the matrix and treat every cell (i, j) as the top-left corner of a potential 3 x 3 region. For each candidate region, verify the constraint by checking all horizontal and vertical adjacent pairs inside the region. There are only a fixed number of comparisons (12 adjacency checks), so validation is constant time. If the region satisfies the threshold condition, compute the sum of the 9 cells and derive the region average using integer division.
Maintain two helper matrices: one for accumulating the sum of region averages affecting each cell and another for counting how many valid regions contributed to that cell. When a valid region is found, add its computed average to all 9 cells and increment their counters. After scanning the entire grid, compute the final result cell-by-cell: if the counter is greater than zero, divide the accumulated sum by the count; otherwise copy the original pixel value.
This approach works well because the region size is fixed. Even though every cell may trigger a region check, each validation and averaging step touches only 9 cells, making the total runtime proportional to the grid size. The technique relies heavily on systematic iteration over a matrix and careful boundary handling.
Approach 2: Prefix Sum Assisted Averaging (O(m*n) time, O(m*n) space)
You can slightly streamline the average calculation by precomputing a 2D prefix sum of the grid. This allows constant-time retrieval of any 3 x 3 region sum instead of summing the nine elements directly. The adjacency validation still requires checking neighbors within the region, but the averaging step becomes a single prefix-sum query.
In practice the improvement is minor because the region size is small, but prefix sums can help if the region size becomes variable in a follow-up question. This pattern appears frequently in array and matrix range-sum problems.
Recommended for interviews: The brute-force region detection approach is typically expected. It demonstrates that you can systematically scan a grid, validate local constraints, and correctly handle overlapping contributions. Prefix sums are a reasonable optimization discussion but rarely necessary given the fixed 3x3 window.
Approach 1: Brute-Force Region Detection
This approach involves iterating over every possible 3x3 subgrid in the image. For each subgrid, check if all adjacent pixels satisfy the threshold condition. If they do, calculate the average intensity of the subgrid and assign it to every pixel in the grid.
For each pixel, we maintain a list of intensities it contributes to, and calculate the final intensity by averaging these contributions.
def is_valid_subgrid(image, si, sj, threshold):
adj = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for i in range(si, si + 3):
for j in range(sj, sj + 3):
for di, dj in adj:
ni, nj = i + di, j + dj
if si <= ni < si + 3 and sj <= nj < sj + 3:
if abs(image[i][j] - image[ni][nj]) > threshold:
return False
return True
def average_subgrid(image, si, sj):
total = sum(image[i][j] for i in range(si, si + 3) for j in range(sj, sj + 3))
return total // 9
def grid_average(image, threshold):
m, n = len(image), len(image[0])
result = [[image[i][j] for j in range(n)] for i in range(m)]
counts = [[0] * n for _ in range(m)]
for i in range(m - 2):
for j in range(n - 2):
if is_valid_subgrid(image, i, j, threshold):
avg = average_subgrid(image, i, j)
for x in range(i, i + 3):
for y in range(j, j + 3):
result[x][y] += avg
counts[x][y] += 1
for i in range(m):
for j in range(n):
if counts[i][j] > 0:
result[i][j] //= counts[i][j]
return result
image = [[5, 6, 7, 10],[8, 9, 10, 10],[11, 12, 13, 10]]
threshold = 3
result = grid_average(image, threshold)
for row in result:
print(row)import java.util.*;
public class GridAverage {
public static boolean isValidSubgrid(int[][] image, int si, int sj, int threshold) {
int[][] adj = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
for (int[] d : adj) {
int ni = i + d[0];
int nj = j + d[1];
if (ni >= si && ni < si + 3 && nj >= sj && nj < sj + 3) {
if (Math.abs(image[i][j] - image[ni][nj]) > threshold) {
return false;
}
}
}
}
}
return true;
}
public static int averageSubgrid(int[][] image, int si, int sj) {
int sum = 0;
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
sum += image[i][j];
}
}
return sum / 9;
}
public static int[][] gridAverage(int[][] image, int threshold) {
int m = image.length;
int n = image[0].length;
int[][] result = new int[m][n];
int[][] counts = new int[m][n];
for (int i = 0; i <= m - 3; i++) {
for (int j = 0; j <= n - 3; j++) {
if (isValidSubgrid(image, i, j, threshold)) {
int avg = averageSubgrid(image, i, j);
for (int x = i; x < i + 3; x++) {
for (int y = j; y < j + 3; y++) {
result[x][y] += avg;
counts[x][y]++;
}
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (counts[i][j] != 0) {
result[i][j] = result[i][j] / counts[i][j];
} else {
result[i][j] = image[i][j];
}
}
}
return result;
}
public static void main(String[] args) {
int[][] image = {
{5, 6, 7, 10},
{8, 9, 10, 10},
{11, 12, 13, 10}
};
int threshold = 3;
int[][] result = gridAverage(image, threshold);
System.out.println("Result:");
for (int[] row : result) {
for (int value : row) {
System.out.print(value + " ");
}
System.out.println();
}
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isValidSubgrid(const vector<vector<int>>& image, int si, int sj, int threshold) {
int adj[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = si; i < si + 3; ++i) {
for (int j = sj; j < sj + 3; ++j) {
for (int k = 0; k < 4; ++k) {
int ni = i + adj[k][0];
int nj = j + adj[k][1];
if (ni >= si && ni < si + 3 && nj >= sj && nj < sj + 3) {
if (abs(image[i][j] - image[ni][nj]) > threshold) {
return false;
}
}
}
}
}
return true;
}
int averageSubgrid(const vector<vector<int>>& image, int si, int sj) {
int sum = 0;
for (int i = si; i < si + 3; ++i) {
for (int j = sj; j < sj + 3; ++j) {
sum += image[i][j];
}
}
return sum / 9;
}
vector<vector<int>> gridAverage(vector<vector<int>>& image, int threshold) {
int m = image.size();
int n = image[0].size();
vector<vector<int>> result(m, vector<int>(n, 0));
vector<vector<int>> counts(m, vector<int>(n, 0));
for (int i = 0; i <= m - 3; ++i) {
for (int j = 0; j <= n - 3; ++j) {
if (isValidSubgrid(image, i, j, threshold)) {
int avg = averageSubgrid(image, i, j);
for (int x = i; x < i + 3; ++x) {
for (int y = j; y < j + 3; ++y) {
result[x][y] += avg;
counts[x][y]++;
}
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (counts[i][j] != 0) {
result[i][j] = floor(result[i][j] / counts[i][j]);
} else {
result[i][j] = image[i][j];
}
}
}
return result;
}
int main() {
vector<vector<int>> image = {
{5, 6, 7, 10},
{8, 9, 10, 10},
{11, 12, 13, 10}
};
int threshold = 3;
vector<vector<int>> result = gridAverage(image, threshold);
cout << "Result:" << endl;
for (const auto& row : result) {
for (int value : row) {
cout << value << " ";
}
cout << endl;
}
return 0;
}function isValidSubgrid(image, si, sj, threshold) {
const adj = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for (let i = si; i < si + 3; i++) {
for (let j = sj; j < sj + 3; j++) {
for (const [di, dj] of adj) {
const ni = i + di;
const nj = j + dj;
if (ni >= si && ni < si + 3 && nj >= sj && nj < sj + 3) {
if (Math.abs(image[i][j] - image[ni][nj]) > threshold) {
return false;
}
}
}
}
}
return true;
}
function averageSubgrid(image, si, sj) {
let sum = 0;
for (let i = si; i < si + 3; i++) {
for (let j = sj; j < sj + 3; j++) {
sum += image[i][j];
}
}
return Math.floor(sum / 9);
}
function gridAverage(image, threshold) {
const m = image.length;
const n = image[0].length;
const result = Array.from({ length: m }, () => Array(n).fill(0));
const counts = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i <= m - 3; i++) {
for (let j = 0; j <= n - 3; j++) {
if (isValidSubgrid(image, i, j, threshold)) {
const avg = averageSubgrid(image, i, j);
for (let x = i; x < i + 3; x++) {
for (let y = j; y < j + 3; y++) {
result[x][y] += avg;
counts[x][y]++;
}
}
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
result[i][j] = counts[i][j] ? Math.floor(result[i][j] / counts[i][j]) : image[i][j];
}
}
return result;
}
const image = [
[5, 6, 7, 10],
[8, 9, 10, 10],
[11, 12, 13, 10]
];
const threshold = 3;
const result = gridAverage(image, threshold);
result.forEach(row => console.log(row));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool is_valid_subgrid(int **image, int si, int sj, int threshold) {
int adj[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
for (int k = 0; k < 4; k++) {
int ni = i + adj[k][0];
int nj = j + adj[k][1];
if (ni >= si && ni < si + 3 && nj >= sj && nj < sj + 3) {
if (abs(image[i][j] - image[ni][nj]) > threshold) {
return false;
}
}
}
}
}
return true;
}
int average_subgrid(int **image, int si, int sj) {
int sum = 0;
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
sum += image[i][j];
}
}
return sum / 9;
}
int** grid_average(int** image, int m, int n, int threshold) {
int** result = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; i++) {
result[i] = (int*)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
result[i][j] = image[i][j];
}
}
for (int i = 0; i <= m - 3; i++) {
for (int j = 0; j <= n - 3; j++) {
if (is_valid_subgrid(image, i, j, threshold)) {
int avg = average_subgrid(image, i, j);
for (int x = i; x < i + 3; x++) {
for (int y = j; y < j + 3; y++) {
result[x][y] = (result[x][y] == image[x][y])
? avg : (result[x][y] + avg) / 2;
}
}
}
}
}
return result;
}
int main() {
int m = 3, n = 4, threshold = 3;
int image_data[3][4] = {
{5, 6, 7, 10},
{8, 9, 10, 10},
{11, 12, 13, 10}
};
int* image_ptrs[m];
for (int i = 0; i < m; i++) {
image_ptrs[i] = image_data[i];
}
int** result = grid_average(image_ptrs, m, n, threshold);
printf("Result:\n");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
for (int i = 0; i < m; i++) {
free(result[i]);
}
free(result);
return 0;
}using System;
public class GridAverage {
public static bool IsValidSubgrid(int[,] image, int si, int sj, int threshold) {
int[,] adj = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
for (int k = 0; k < 4; k++) {
int ni = i + adj[k, 0];
int nj = j + adj[k, 1];
if (ni >= si && ni < si + 3 && nj >= sj && nj < sj + 3) {
if (Math.Abs(image[i, j] - image[ni, nj]) > threshold) {
return false;
}
}
}
}
}
return true;
}
public static int AverageSubgrid(int[,] image, int si, int sj) {
int sum = 0;
for (int i = si; i < si + 3; i++) {
for (int j = sj; j < sj + 3; j++) {
sum += image[i, j];
}
}
return sum / 9;
}
public static int[,] GridAverage(int[,] image, int threshold) {
int m = image.GetLength(0);
int n = image.GetLength(1);
int[,] result = new int[m, n];
int[,] counts = new int[m, n];
for (int i = 0; i <= m - 3; i++) {
for (int j = 0; j <= n - 3; j++) {
if (IsValidSubgrid(image, i, j, threshold)) {
int avg = AverageSubgrid(image, i, j);
for (int x = i; x < i + 3; x++) {
for (int y = j; y < j + 3; y++) {
result[x, y] += avg;
counts[x, y]++;
}
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (counts[i, j] != 0) {
result[i, j] = result[i, j] / counts[i, j];
} else {
result[i, j] = image[i, j];
}
}
}
return result;
}
public static void Main(String[] args) {
int[,] image = {
{5, 6, 7, 10},
{8, 9, 10, 10},
{11, 12, 13, 10}
};
int threshold = 3;
int[,] result = GridAverage(image, threshold);
Console.WriteLine("Result:");
for (int i = 0; i < result.GetLength(0); i++) {
for (int j = 0; j < result.GetLength(1); j++) {
Console.Write(result[i, j] + " ");
}
Console.WriteLine();
}
}
}The Python solution utilizes list comprehensions and built-in functions for concise subgrid verification and average calculation. Each element begins as a copy of the input image and is potentially updated if it is part of valid 3x3 regions that satisfy the intensity difference threshold. Pixel averages are calculated in-place, accounting for overlapping subgrid contributions, before a final normalization step.
Time Complexity: O(m * n), governed by double nesting over the image dimensions.
Space Complexity: O(m * n) due to the result and count matrices.
Approach 2: Default Approach
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute-Force Region Detection | Time Complexity: O(m * n), governed by double nesting over the image dimensions. Space Complexity: O(m * n) due to the result and count matrices. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-Force 3x3 Region Detection | O(m*n) | O(m*n) | Best general solution since each region has constant size and validation is simple. |
| Prefix Sum Assisted Averaging | O(m*n) | O(m*n) | Useful when region sizes vary or when many range-sum queries are required. |
Frequently asked questions
Is Find the Grid of Region Average easy or hard?
Find the Grid of Region Average is generally classified as a medium difficulty problem. The main challenge is correctly validating adjacency constraints within each 3x3 region and properly averaging overlapping region contributions without double-counting.
Find the Grid of Region Average Python/Java solution
In Python or Java, iterate over all possible 3x3 region start positions, validate the threshold condition by comparing adjacent cells, compute the floor average, and update two helper matrices for sum and count. After processing all regions, compute the final value for each cell based on how many valid regions contributed to it.
How to solve Find the Grid of Region Average in O(n)?
Treat the grid as a collection of fixed 3x3 windows and iterate through all valid starting positions. For each window, verify adjacency constraints and compute the average of the nine elements. Because the window size is constant, the total work scales linearly with the number of cells, giving O(m*n) complexity.
What is the best approach for Find the Grid of Region Average?
The standard solution scans every possible 3x3 region in the matrix and validates whether all adjacent cells differ by at most the threshold. If valid, compute the region average and distribute it to the nine cells while tracking contributions. This brute-force region detection works in O(m*n) time because each region has constant size.
Is Find the Grid of Region Average asked at Google/Amazon/Meta?
Matrix scanning and region validation problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the same skills—grid traversal, local constraint checks, and handling overlapping regions—are commonly tested.
What data structure is used in Find the Grid of Region Average?
The solution primarily uses a 2D matrix along with two auxiliary matrices to track accumulated region averages and contribution counts. Some optimized variants also use a 2D prefix sum structure to compute region sums faster.
What is the time complexity of Find the Grid of Region Average?
The typical implementation runs in O(m*n) time where m and n are the grid dimensions. Each cell is considered as the top-left corner of a 3x3 region, and validating the region requires a constant number of comparisons and additions. Extra arrays used to accumulate region averages add O(m*n) space.