3030. Find the Grid of Region Average

MediumArrayMatrix
Leetcode Link

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 the abs() 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 in ct.

After the regions have been processed, we perform a final pass over the entire grid:

  • For each pixel (i, j), we check ct[i][j]. If it's greater than zero, it means the pixel is part of one or more regions. We then finalize ans[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 from image[i][j] to ans[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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's assume we have the following 5x5 grayscale image image represented by a 2D grid and a threshold of 10:

1image = [
2    [100, 105, 102, 200, 205],
3    [103, 108, 103, 205, 200],
4    [101, 106, 102, 202, 207],
5    [104, 109, 104, 210, 205],
6    [100, 105, 107, 205, 200]
7]
8threshold = 10

In this example, we will find the regions and calculate the resulting grid result.

  1. Initialize the auxiliary grids ans and ct to zeros:
1ans = [
2    [0, 0, 0, 0, 0],
3    [0, 0, 0, 0, 0],
4    [0, 0, 0, 0, 0],
5    [0, 0, 0, 0, 0],
6    [0, 0, 0, 0, 0]
7]
8ct = [
9    [0, 0, 0, 0, 0],
10    [0, 0, 0, 0, 0],
11    [0, 0, 0, 0, 0],
12    [0, 0, 0, 0, 0],
13    [0, 0, 0, 0, 0]
14]
  1. 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 if i is 0, 1, 2, 3 and j is 0, 1, 2, 3. For example, starting at the top-left corner (0, 0), let's check if it can be a region:
1Top-left corner (0, 0) region:
2[
3    [100, 105, 102],
4    [103, 108, 103],
5    [101, 106, 102]
6]
  • 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):

1Sum = 100 + 105 + 102 + 103 + 108 + 103 + 101 + 106 + 102 = 930
2Average = floor(930 / 9) = floor(103.33) = 103
  • We distribute this average to all 9 pixels of the ans matrix and increment ct for each:
1ans after processing top-left corner (0, 0):
2[
3    [103, 103, 103,   0,   0],
4    [103, 103, 103,   0,   0],
5    [103, 103, 103,   0,   0],
6    [  0,   0,   0,   0,   0],
7    [  0,   0,   0,   0,   0]
8]
9ct after processing top-left corner (0, 0):
10[
11    [1, 1, 1, 0, 0],
12    [1, 1, 1, 0, 0],
13    [1, 1, 1, 0, 0],
14    [0, 0, 0, 0, 0],
15    [0, 0, 0, 0, 0]
16]
  • 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.
  1. After determining all potential regions, process each pixel to compute the final values in result.
  • For each pixel (i, j), if ct[i][j] is greater than zero, result[i][j] is set to floor(ans[i][j] / ct[i][j]).
  • If ct[i][j] is zero, result[i][j] remains as image[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 occupies O(n * m) space.
  • The ct array holds the count of how many times a cell value has been included in a sum, which also occupies O(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.


Fast Track Your Learning with Our Quick Skills Quiz:

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


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄