3030. Find the Grid of Region Average
Problem Description
You are given a grayscale image that is represented by a 2D grid image
where the intensity of each pixel is a value between 0 and 255. The grid is 0-indexed, which means that the row and column indices start from 0. Additionally, you are given a non-negative integer threshold
.
The problem involves finding regions within this image grid. A region is defined as a 3x3 subgrid where the absolute difference in intensity between any two adjacent pixels is less than or equal to the threshold
. A pixel is adjacent to another if it is directly above, below, to the left, or to the right of the other pixel. It's important to note that a single pixel can be part of multiple regions.
You are required to create a new grid result
where each entry result[i][j]
represents the average intensity of the region(s) to which the pixel at image[i][j]
belongs. If a pixel belongs to multiple regions, you should take the average of the rounded down averages for those regions and then round down this final value. If a pixel does not belong to any region, result[i][j]
should simply be the original intensity from image[i][j]
.
The goal is to calculate this result grid given the image grid and the threshold.
Intuition
The main intuition behind the solution is to iterate over the image grid and identify the 3x3 subgrids that qualify as regions based on the given threshold condition. Once we identify such a region, we compute its average pixel intensity.
We maintain two auxiliary grids: ans
, which keeps the sum of average intensities of the regions that each pixel belongs to, and ct
, which counts the number of regions each pixel is a part of.
We loop through each possible top-left coordinate (i, j)
of a potential 3x3 region in the image. For each position, we check if every pair of adjacent pixels within the 3x3 subgrid satisfies the threshold condition. If they do, we have found a valid region, and we calculate the sum of pixel intensities for this region.
For each pixel within this region, we add the floor of the region's average intensity to the corresponding position in ans
, and increment the region count in ct
. After all potential regions have been processed, we go through every pixel in the image. If a pixel was part of at least one region (ct[i][j]
is not zero), we update result[i][j]
to be the floor of the average of the sums from ans
divided by the count from ct
. If a pixel was not part of any region, we just set result[i][j]
to the original pixel intensity image[i][j]
.
The approach leverages the idea that a pixel can be part of multiple regions and ensures that its final intensity in result
is an average of those regions' intensities, rounded down as specified in the problem statement.
Solution Approach
The implementation utilizes nested for-loops to iterate over possible top-left corners (i, j)
of potential 3x3 regions within the image
. It uses a set of additional nested loops to check the conditions for identifying a region and to compute the total intensity and update the ans
and ct
auxiliary matrices.
Firstly, the algorithm establishes two matrices, ans
and ct
, both the size of the original image
grid, initialized to zeroes. These matrices serve two purposes:
ans[i][j]
holds the cumulative sum of average intensities for the pixel at(i, j)
for all regions it belongs to.ct[i][j]
holds the count of regions that the pixel at(i, j)
is part of.
Next, we begin our core logic, walking the image grid for potential regions:
- Loop through each cell
(i, j)
of the grid, excluding the last two rows and columns since a 3x3 region cannot start there (would extend beyond grid boundaries). - For each potential region's top-left corner, we assess if the pixels within this 3x3 subgrid form a valid region by comparing each adjacent pair of pixels and checking whether their intensity difference is within the
threshold
. This is done using additional loops and theabs()
function. - If we confirm a valid region, we sum the intensities of all nine pixels within this 3x3 subgrid.
- We then distribute this total sum (averaged by dividing by 9 and taking the floor) across the nine corresponding cells in the
ans
matrix and increment the counts inct
.
After the regions have been processed, we perform a final pass over the entire grid:
- For each pixel
(i, j)
, we checkct[i][j]
. If it's greater than zero, it means the pixel is part of one or more regions. We then finalizeans[i][j]
by dividing the accumulated sum by the count (the number of regions the pixel belongs to) and rounding down. - If
ct[i][j]
is zero, we simply assign the original intensity value fromimage[i][j]
toans[i][j]
, as the pixel wasn't part of any region.
The resultant ans
matrix now reflects the average intensities as required by the problem, and this matrix is returned as the final answer.
The algorithm is straightforward but computationally intensive given the nested loops, which could lead to a higher time complexity, particularly for larger images.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we have the following 5x5 grayscale image image
represented by a 2D grid and a threshold
of 10:
image = [ [100, 105, 102, 200, 205], [103, 108, 103, 205, 200], [101, 106, 102, 202, 207], [104, 109, 104, 210, 205], [100, 105, 107, 205, 200] ] threshold = 10
In this example, we will find the regions and calculate the resulting grid result
.
- Initialize the auxiliary grids
ans
andct
to zeros:
ans = [ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ] ct = [ [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ]
- Loop through the potential top-left corners of the 3x3 regions (excluding the last two rows and columns since a 3x3 region cannot start there):
- Any given cell
(i, j)
can be part of a region ifi
is 0, 1, 2, 3 andj
is 0, 1, 2, 3. For example, starting at the top-left corner(0, 0)
, let's check if it can be a region:
Top-left corner (0, 0) region: [ [100, 105, 102], [103, 108, 103], [101, 106, 102] ]
-
We compare each pair of adjacent pixels within this 3x3 grid to see if their absolute difference is less than or equal to 10. In this case, all pairs satisfy the condition, so this is a valid region.
-
Compute the sum of pixel intensities in the region and divide by 9 (floor if necessary):
Sum = 100 + 105 + 102 + 103 + 108 + 103 + 101 + 106 + 102 = 930 Average = floor(930 / 9) = floor(103.33) = 103
- We distribute this average to all 9 pixels of the
ans
matrix and incrementct
for each:
ans after processing top-left corner (0, 0): [ [103, 103, 103, 0, 0], [103, 103, 103, 0, 0], [103, 103, 103, 0, 0], [ 0, 0, 0, 0, 0], [ 0, 0, 0, 0, 0] ] ct after processing top-left corner (0, 0): [ [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0] ]
- This process continues for other top-left corners, such as (0, 1), (1, 0), etc., until all possible starting points for regions have been checked.
- After determining all potential regions, process each pixel to compute the final values in
result
.
- For each pixel
(i, j)
, ifct[i][j]
is greater than zero,result[i][j]
is set tofloor(ans[i][j] / ct[i][j])
. - If
ct[i][j]
is zero,result[i][j]
remains asimage[i][j]
.
The final ans
matrix is the output of the solution, showcasing the average intensities of pixels across their respective regions, rounded according to the rules specified in the problem description.
Solution Implementation
1from typing import List
2
3class Solution:
4 def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
5 # Get the number of rows and columns of the image
6 rows, cols = len(image), len(image[0])
7
8 # Initialize the answer grid with zeros
9 answer_grid = [[0] * cols for _ in range(rows)]
10
11 # Initialize a count grid to keep track of the number of times each pixel's
12 # value has been added to the answer grid
13 count_grid = [[0] * cols for _ in range(rows)]
14
15 # Iterate over each 3x3 region in the image
16 for i in range(rows - 2):
17 for j in range(cols - 2):
18 # Flag to check if the region meets the threshold requirement
19 region_valid = True
20
21 # Check differences within rows of the 3x3 region
22 for k in range(3):
23 for l in range(2):
24 region_valid &= (
25 abs(image[i + k][j + l] - image[i + k][j + l + 1])
26 <= threshold
27 )
28
29 # Check differences within columns of the 3x3 region
30 for k in range(2):
31 for l in range(3):
32 region_valid &= (
33 abs(image[i + k][j + l] - image[i + k + 1][j + l])
34 <= threshold
35 )
36
37 # If the region is valid, compute the average value of the 3x3 region
38 if region_valid:
39 # Sum all pixel values within the region
40 total = sum(image[i + k][j + l] for k in range(3) for l in range(3))
41 # Update the answer and count grids
42 for k in range(3):
43 for l in range(3):
44 count_grid[i + k][j + l] += 1
45 answer_grid[i + k][j + l] += total // 9 # Integer division
46
47 # Adjust the values in the answer grid based on counts or fallback to original image
48 for i in range(rows):
49 for j in range(cols):
50 if count_grid[i][j] == 0:
51 # If the pixel was never part of a valid region, use the original value
52 answer_grid[i][j] = image[i][j]
53 else:
54 # Otherwise, divide by the count to get the average
55 answer_grid[i][j] //= count_grid[i][j]
56
57 return answer_grid
58
1class Solution {
2 public int[][] resultGrid(int[][] image, int threshold) {
3 // Get the dimensions of the image
4 int rows = image.length;
5 int cols = image[0].length;
6
7 // Initialize the answer and count grid with the same dimensions
8 int[][] answer = new int[rows][cols];
9 int[][] count = new int[rows][cols];
10
11 // Loop through the image by considering a 3x3 region
12 for (int i = 0; i + 2 < rows; ++i) {
13 for (int j = 0; j + 2 < cols; ++j) {
14 // Assume the current 3x3 region meets the condition
15 boolean isSmoothRegion = true;
16
17 // Check if each pair of pixels horizontally within the 3x3 block satisfies the threshold
18 for (int k = 0; k < 3; ++k) {
19 for (int l = 0; l < 2; ++l) {
20 isSmoothRegion
21 &= Math.abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
22 }
23 }
24 // Check if each pair of pixels vertically within the 3x3 block satisfies the threshold
25 for (int k = 0; k < 2; ++k) {
26 for (int l = 0; l < 3; ++l) {
27 isSmoothRegion
28 &= Math.abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
29 }
30 }
31 // If the 3x3 region is smooth, calculate the average of the region and add it to the answer grid
32 if (isSmoothRegion) {
33 // Compute total sum of the 3x3 block
34 int total = 0;
35 for (int k = 0; k < 3; ++k) {
36 for (int l = 0; l < 3; ++l) {
37 total += image[i + k][j + l];
38 }
39 }
40 // Update the answer and count grids for each cell in the 3x3 block
41 for (int k = 0; k < 3; ++k) {
42 for (int l = 0; l < 3; ++l) {
43 count[i + k][j + l]++;
44 answer[i + k][j + l] += total / 9;
45 }
46 }
47 }
48 }
49 }
50
51 // Go through every cell in the grids to finalize the answer grid values
52 for (int i = 0; i < rows; ++i) {
53 for (int j = 0; j < cols; ++j) {
54 // If the count for a cell is zero, use original image value
55 if (count[i][j] == 0) {
56 answer[i][j] = image[i][j];
57 } else {
58 // Otherwise, average the sum by the count for the cell
59 answer[i][j] /= count[i][j];
60 }
61 }
62 }
63
64 // Return the computed answer grid
65 return answer;
66 }
67}
68
1class Solution {
2public:
3 // Process the given image and return the adjusted grid based on the threshold
4 vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
5 int rows = image.size(), cols = image[0].size(); // Get the dimensions of the image
6 vector<vector<int>> ans(rows, vector<int>(cols)); // Initialize the result grid
7 vector<vector<int>> count(rows, vector<int>(cols)); // Initialize a grid to keep track of counts
8
9 // Check 3x3 regions within the grid
10 for (int i = 0; i + 2 < rows; ++i) {
11 for (int j = 0; j + 2 < cols; ++j) {
12 bool regionIsWithinThreshold = true; // Flag to indicate if the 3x3 region satisfies the condition
13
14 // Check differences between horizontally adjacent pixels
15 for (int k = 0; k < 3; ++k) {
16 for (int l = 0; l < 2; ++l) {
17 regionIsWithinThreshold &= abs(image[i + k][j + l] - image[i + k][j + l + 1]) <= threshold;
18 }
19 }
20
21 // Check differences between vertically adjacent pixels
22 for (int k = 0; k < 2; ++k) {
23 for (int l = 0; l < 3; ++l) {
24 regionIsWithinThreshold &= abs(image[i + k][j + l] - image[i + k + 1][j + l]) <= threshold;
25 }
26 }
27
28 // If the condition is satisfied, update the result grid and counts
29 if (regionIsWithinThreshold) {
30 int total = 0; // Calculate the sum of pixel values in the 3x3 region
31 for (int k = 0; k < 3; ++k) {
32 for (int l = 0; l < 3; ++l) {
33 total += image[i + k][j + l];
34 }
35 }
36
37 // Distribute the average value of the region to the result grid
38 for (int k = 0; k < 3; ++k) {
39 for (int l = 0; l < 3; ++l) {
40 count[i + k][j + l]++;
41 ans[i + k][j + l] += total / 9; // Divide by 9 to get the average pixel value
42 }
43 }
44 }
45 }
46 }
47
48 // Normalize the result grid by dividing by the count
49 for (int i = 0; i < rows; ++i) {
50 for (int j = 0; j < cols; ++j) {
51 if (count[i][j] == 0) { // If no regions affected the pixel, keep the original value
52 ans[i][j] = image[i][j];
53 } else { // Otherwise, divide by the count to get the average
54 ans[i][j] /= count[i][j];
55 }
56 }
57 }
58
59 return ans; // Return the final processed grid
60 }
61};
62
1function resultGrid(image: number[][], threshold: number): number[][] {
2 const rows: number = image.length;
3 const cols: number = image[0].length;
4 const answerGrid: number[][] = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
5 const countGrid: number[][] = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
6
7 // Iterate over each 3x3 region of the image grid
8 for (let i = 0; i + 2 < rows; ++i) {
9 for (let j = 0; j + 2 < cols; ++j) {
10 let isRegionUniform: boolean = true;
11
12 // Check if all horizontal pairs within the current 3x3 region meet the threshold condition
13 for (let rowOffset = 0; rowOffset < 3; ++rowOffset) {
14 for (let colOffset = 0; colOffset < 2; ++colOffset) {
15 if (Math.abs(image[i + rowOffset][j + colOffset] - image[i + rowOffset][j + colOffset + 1]) > threshold) {
16 isRegionUniform = false;
17 }
18 }
19 }
20
21 // Check if all vertical pairs within the current 3x3 region meet the threshold condition
22 for (let rowOffset = 0; rowOffset < 2; ++rowOffset) {
23 for (let colOffset = 0; colOffset < 3; ++colOffset) {
24 if (Math.abs(image[i + rowOffset][j + colOffset] - image[i + rowOffset + 1][j + colOffset]) > threshold) {
25 isRegionUniform = false;
26 }
27 }
28 }
29
30 // If region is uniform, update the answer and count grids
31 if (isRegionUniform) {
32 let total: number = 0;
33
34 // Calculate the sum of pixel values in the 3x3 region
35 for (let rowOffset = 0; rowOffset < 3; ++rowOffset) {
36 for (let colOffset = 0; colOffset < 3; ++colOffset) {
37 total += image[i + rowOffset][j + colOffset];
38 }
39 }
40 let avgValue = Math.floor(total / 9);
41
42 // Update the answer and count grids with the calculated average value
43 for (let rowOffset = 0; rowOffset < 3; ++rowOffset) {
44 for (let colOffset = 0; colOffset < 3; ++colOffset) {
45 countGrid[i + rowOffset][j + colOffset]++;
46 answerGrid[i + rowOffset][j + colOffset] += avgValue;
47 }
48 }
49 }
50 }
51 }
52
53 // Compute final averaged values for the answer grid
54 for (let i = 0; i < rows; ++i) {
55 for (let j = 0; j < cols; ++j) {
56 if (countGrid[i][j] === 0) {
57 answerGrid[i][j] = image[i][j];
58 } else {
59 answerGrid[i][j] = Math.floor(answerGrid[i][j] / countGrid[i][j]);
60 }
61 }
62 }
63 return answerGrid;
64}
65
Time and Space Complexity
The given Python code defines a method resultGrid
that modifies a grid image
based on a certain threshold
. It also calculates the average value of a region that fits the given condition.
Time Complexity
The time complexity of this code involves several nested loops:
- There are two external loops over the rows and columns (except for the last two), which give us
O((n-2) * (m-2))
. - Inside these loops, there are two more nested loops to check the threshold condition for each 3x3 region, which always check 8 differences, resulting in
O(8)
operations per region. - Then again, it iterates over the 3x3 region, this time to sum the values and to increment the count; this is
O(9)
for each region.
The combined time complexity when considering the nested loops for threshold checking and summing over the 3x3 region is O(8 + 9)
. However, since these are constants, they do not affect the asymptotic behavior compared to the number of times the loops are executed, which depends on the dimensions of the image (n, m)
.
Therefore, combining all these, the overall time complexity is O((n-2) * (m-2))
, which simplifies to O(n * m)
as n
and m
become large.
Lastly, there is one final loop which iterates over all the cells to adjust the final values based on the count ct
, which has a time complexity of O(n * m)
.
When combined, since these operations are sequential, the overall time complexity remains O(n * m)
.
Space Complexity
The space complexity is determined by the additional space used by the algorithm, which is not inclusive of the input itself:
- The
ans
array holds the modified image data, which occupiesO(n * m)
space. - The
ct
array holds the count of how many times a cell value has been included in a sum, which also occupiesO(n * m)
space.
Adding these together, the total space required for the algorithm is 2 * O(n * m)
, but we drop the constant in Big O notation, rendering the space complexity to O(n * m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!