Find the Grid of Region Average

Medium

Asked by:

26 views

Topics:

Arrays

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 <= 500
0 <= image[i][j] <= 255
0 <= threshold <= 255

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What data type are the values in the grid (e.g., integers, floats), and what is the range of possible values?
Can the dimensions of the grid be zero? What should I return if the grid is empty?
What size should the region be? Is it always a square, or can it be rectangular? Is the size given as input, or is it a fixed constant?
How should I handle edge cases where the region extends beyond the boundaries of the grid? Should I use only the values within the grid, or pad the grid in some way?
What is the expected output format? Should the output grid be a new grid or modifications to the original, and what data type should the average values be (e.g., integers, floats)?

Brute Force Solution

Approach

We're going to calculate the average of each cell's surrounding region in a grid. The brute force method calculates each average completely independently without trying to reuse any calculations.

Here's how the algorithm would work step-by-step:

For each cell in the grid, we'll look at its neighbors.
To determine the neighbors, we'll look at the cells above, below, to the left, to the right, and diagonally from the current cell, but only if those cells are actually inside the grid's boundaries.
We'll add up the values of all the neighbors we find, including the cell itself.
We'll count how many neighbors we added up.
We'll divide the sum of the neighbor's values by the number of neighbors to find the average.
We'll repeat this process for every single cell in the grid, and the result of all the averages will be our answer.

Code Implementation

def find_grid_of_region_average(grid):
    rows = len(grid)
    cols = len(grid[0])
    average_grid = [[0.0] * cols for _ in range(rows)]

    for row_index in range(rows):
        for col_index in range(cols):
            neighbor_sum = 0
            neighbor_count = 0

            # Iterate through neighbors, including the cell itself
            for neighbor_row in range(max(0, row_index - 1), min(rows, row_index + 2)):

                for neighbor_col in range(max(0, col_index - 1), min(cols, col_index + 2)):
                    neighbor_sum += grid[neighbor_row][neighbor_col]
                    neighbor_count += 1

            # Avoid division by zero for empty grids.
            if neighbor_count > 0:

                average_grid[row_index][col_index] = float(neighbor_sum) / neighbor_count

            # Assign zero if no neighbors were found
            else:

                average_grid[row_index][col_index] = 0.0

    return average_grid

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each cell in the grid. If we assume the grid has dimensions m x k, where n is the total number of cells (n = m * k), the outer loop iterates 'n' times (once for each cell). For each cell, it calculates the average of its neighbors which involves, at most, a constant number of operations (checking up to 8 neighbors and the cell itself, summing their values, and dividing by the count). Since the number of operations inside the outer loop is constant, the overall time complexity is proportional to the number of cells, which is O(n). In the common case where the grid is square with side 's' and n = s*s, this is O(s²). Since the input size is n (the number of cells), the time complexity can be expressed as O(n).

Space Complexity

O(N) – The algorithm calculates the average for each cell in the grid and stores the result. A new grid of the same dimensions as the input grid is created to store these average values. If the input grid has N cells (where N is the number of rows multiplied by the number of columns), then the output grid will also have N cells, each holding the calculated average. Thus, the auxiliary space used is proportional to the number of cells in the input grid, resulting in a space complexity of O(N).

Optimal Solution

Approach

The key is to avoid recalculating sums repeatedly. Instead, we precompute the sums of all rectangular regions using a clever trick called a cumulative sum, and then use these precomputed sums to quickly calculate the average of any region we need.

Here's how the algorithm would work step-by-step:

First, create a new grid where each cell stores the sum of all numbers in the original grid from the top-left corner up to that cell.
To fill this new grid, start with the top-left cell, which is just the value of the original cell. Then, for each other cell, its value is the original cell's value plus the value above it plus the value to the left of it, minus the value diagonally above and to the left (to avoid counting that twice).
Now, to find the average of a region, use the cumulative sum grid. Find the cumulative sums at the bottom-right, top-right, bottom-left, and top-left corners of the region we are interested in.
Calculate the sum of the region using the formula: (bottom-right cumulative sum) - (top-right cumulative sum) - (bottom-left cumulative sum) + (top-left cumulative sum before the region).
Divide this sum by the number of cells in the region to get the average. This can be done by multiplying the height and width of the region.
Repeat this process for every cell in the original grid to create the grid of region averages. Each average comes from a 3x3 region centered around that cell.

Code Implementation

def find_grid_of_region_average(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0

    cumulative_sum_grid = [[0] * cols for _ in range(rows)]

    # Build the cumulative sum grid to optimize sum calculations.
    for row_index in range(rows):
        for col_index in range(cols):
            cumulative_sum_grid[row_index][col_index] = grid[row_index][col_index]
            if row_index > 0:
                cumulative_sum_grid[row_index][col_index] += cumulative_sum_grid[row_index - 1][col_index]
            if col_index > 0:
                cumulative_sum_grid[row_index][col_index] += cumulative_sum_grid[row_index][col_index - 1]
            if row_index > 0 and col_index > 0:
                cumulative_sum_grid[row_index][col_index] -= cumulative_sum_grid[row_index - 1][col_index - 1]

    average_grid = [[0.0] * cols for _ in range(rows)]

    for row_index in range(rows):
        for col_index in range(cols):
            top_row = max(0, row_index - 1)
            bottom_row = min(rows - 1, row_index + 1)
            left_col = max(0, col_index - 1)
            right_col = min(cols - 1, col_index + 1)

            region_height = bottom_row - top_row + 1
            region_width = right_col - left_col + 1
            region_area = region_height * region_width

            bottom_right_sum = cumulative_sum_grid[bottom_row][right_col]
            top_right_sum = cumulative_sum_grid[top_row - 1][right_col] if top_row > 0 else 0
            bottom_left_sum = cumulative_sum_grid[bottom_row][left_col - 1] if left_col > 0 else 0
            top_left_sum = cumulative_sum_grid[top_row - 1][left_col - 1] if top_row > 0 and left_col > 0 else 0

            # Use cumulative sums to efficiently calc region sum
            region_sum = bottom_right_sum - top_right_sum - bottom_left_sum + top_left_sum

            average_grid[row_index][col_index] = float(region_sum) / region_area

    return average_grid

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm first constructs a cumulative sum grid. This involves iterating through each cell of the original grid once, which takes O(n*m) time where n is the number of rows and m is the number of columns. After constructing the cumulative grid, the algorithm iterates through each cell of the original grid again to compute the average of the 3x3 region centered at that cell. Calculating the average using the cumulative sum grid involves a constant number of operations (accessing four cells and performing arithmetic), but is done once for each cell in the grid. Therefore the second step is also O(n*m). Since O(n*m) + O(n*m) simplifies to O(n*m), the overall time complexity is O(n*m).

Space Complexity

O(N*M) – The algorithm creates a cumulative sum grid of the same dimensions as the input grid (N rows and M columns). This cumulative sum grid stores intermediate sums and is the primary source of auxiliary space. The size of this grid is directly proportional to the product of the number of rows and columns in the input grid, hence N*M. Therefore, the auxiliary space complexity is O(N*M), where N represents the number of rows and M represents the number of columns.

Edge Cases

Case	How to Handle
Null or empty input grid	Return an empty grid or null indicating no region averages can be computed.
Grid with only one row or one column	Return the original grid as each cell is its own region.
Grid with all identical values	The region averages will be the same as the initial values, resulting in the same grid.
Grid with large values that might lead to integer overflow when summing	Use a data type with a larger range (e.g., long) for intermediate sums to prevent overflow.
Cells on the border of the grid need special handling for their neighborhood	Conditionally include neighbors only if they are within the bounds of the grid.
Negative numbers in the grid	The averaging process handles negative numbers correctly, no special case is needed.
Extremely large grid dimensions that may cause memory issues	Consider using an in-place algorithm (if possible) or processing the grid in chunks if memory is a constraint.
Floating-point precision issues when calculating the average	Be mindful of potential rounding errors and use appropriate rounding techniques if necessary.

Null or empty input grid

How to Handle:

Return an empty grid or null indicating no region averages can be computed.

Grid with only one row or one column

How to Handle:

Return the original grid as each cell is its own region.

Grid with all identical values

How to Handle:

The region averages will be the same as the initial values, resulting in the same grid.

Grid with large values that might lead to integer overflow when summing

How to Handle:

Use a data type with a larger range (e.g., long) for intermediate sums to prevent overflow.

Cells on the border of the grid need special handling for their neighborhood

How to Handle:

Conditionally include neighbors only if they are within the bounds of the grid.

Negative numbers in the grid

How to Handle:

The averaging process handles negative numbers correctly, no special case is needed.

Extremely large grid dimensions that may cause memory issues

How to Handle:

Consider using an in-place algorithm (if possible) or processing the grid in chunks if memory is a constraint.

Floating-point precision issues when calculating the average

How to Handle:

Be mindful of potential rounding errors and use appropriate rounding techniques if necessary.