3030. Find the Grid of Region Average LeetCode Solution
In this guide, you will get 3030. Find the Grid of Region Average LeetCode Solution with the best time and space complexity. The solution to Find the Grid of Region Average problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Grid of Region Average
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.
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.
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 <= 500
0 <= image[i][j] <= 255
0 <= threshold <= 255
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
3030. Find the Grid of Region Average LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
const int m = image.size();
const int n = image[0].size();
vector<vector<int>> sums(m, vector<int>(n));
vector<vector<int>> counts(m, vector<int>(n));
for (int i = 0; i < m - 2; ++i)
for (int j = 0; j < n - 2; ++j)
if (isRegion(image, i, j, threshold)) {
const int subgridSum = getSubgridSum(image, i, j);
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y) {
sums[x][y] += subgridSum / 9;
counts[x][y] += 1;
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (counts[i][j] > 0)
image[i][j] = sums[i][j] / counts[i][j];
return image;
}
private:
// Returns true if image[i..i + 2][j..j + 2] is a region.
bool isRegion(const vector<vector<int>>& image, int i, int j, int threshold) {
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y) {
if (x > i && abs(image[x][y] - image[x - 1][y]) > threshold)
return false;
if (y > j && abs(image[x][y] - image[x][y - 1]) > threshold)
return false;
}
return true;
}
// Returns the sum of image[i..i + 2][j..j + 2].
int getSubgridSum(const vector<vector<int>>& image, int i, int j) {
int subgridSum = 0;
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y)
subgridSum += image[x][y];
return subgridSum;
}
}; /* code provided by PROGIEZ */
3030. Find the Grid of Region Average LeetCode Solution in Java
class Solution {
public int[][] resultGrid(int[][] image, int threshold) {
final int m = image.length;
final int n = image[0].length;
int[][] sums = new int[m][n];
int[][] counts = new int[m][n];
for (int i = 0; i < m - 2; ++i)
for (int j = 0; j < n - 2; ++j)
if (isRegion(image, i, j, threshold)) {
final int subgridSum = getSubgridSum(image, i, j);
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y) {
sums[x][y] += subgridSum / 9;
counts[x][y] += 1;
}
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (counts[i][j] > 0)
image[i][j] = sums[i][j] / counts[i][j];
return image;
}
// Returns true if image[i..i + 2][j..j + 2] is a region.
private boolean isRegion(int[][] image, int i, int j, int threshold) {
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y) {
if (x > i && Math.abs(image[x][y] - image[x - 1][y]) > threshold)
return false;
if (y > j && Math.abs(image[x][y] - image[x][y - 1]) > threshold)
return false;
}
return true;
}
// Returns the sum of image[i..i + 2][j..j + 2].
private int getSubgridSum(int[][] image, int i, int j) {
int subgridSum = 0;
for (int x = i; x < i + 3; ++x)
for (int y = j; y < j + 3; ++y)
subgridSum += image[x][y];
return subgridSum;
}
} // code provided by PROGIEZ
3030. Find the Grid of Region Average LeetCode Solution in Python
class Solution:
def resultGrid(
self,
image: list[list[int]],
threshold: int,
) -> list[list[int]]:
m = len(image)
n = len(image[0])
sums = [[0] * n for _ in range(m)]
counts = [[0] * n for _ in range(m)]
for i in range(m - 2):
for j in range(n - 2):
if self._isRegion(image, i, j, threshold):
subgridSum = sum(image[x][y]
for x in range(i, i + 3)
for y in range(j, j + 3))
for x in range(i, i + 3):
for y in range(j, j + 3):
sums[x][y] += subgridSum // 9
counts[x][y] += 1
for i in range(m):
for j in range(n):
if counts[i][j] > 0:
image[i][j] = sums[i][j] // counts[i][j]
return image
def _isRegion(
self,
image: list[list[int]],
i: int,
j: int,
threshold: int,
) -> bool:
"""Returns True if image[i..i + 2][j..j + 2] is a region."""
for x in range(i, i + 3):
for y in range(j, j + 3):
if x > i and abs(image[x][y] - image[x - 1][y]) > threshold:
return False
if y > j and abs(image[x][y] - image[x][y - 1]) > threshold:
return False
return True # code by PROGIEZ
