We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Grid of Region Average

Number: 3272

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Given an m x n grid image representing a grayscale image (where each pixel is an integer in the range [0, 255]) and a non-negative integer threshold, determine for each pixel the average intensity of the valid 3x3 regions it belongs to. A 3x3 subgrid qualifies as a region only if for every pair of adjacent pixels (sharing an edge) in that subgrid the absolute intensity difference is less than or equal to threshold. Each region’s average intensity is computed by summing its 9 values and taking the floor of the average. If a pixel belongs to multiple regions, its output value is the floor of the average of all (already floored) region averages. If a pixel does not belong to any region, its value remains unchanged.

Key Insights

  • Only consider 3x3 subgrids, ensuring that each adjacent (up, down, left, right) pair in the subgrid meets the intensity difference condition.
  • For each valid 3x3 region, compute the floor-averaged intensity.
  • Use auxiliary grids to accumulate the sum of region averages and counts for each pixel as regions may overlap.
  • Final pixel value becomes the floor of (total region average sum divided by count) if at least one region covers that pixel; otherwise, it remains as in the original image.

Space and Time Complexity

Time Complexity: O(m * n) – iterating over each possible 3x3 subgrid and updating overlapping pixels, with constant additional work per subgrid.
Space Complexity: O(m * n) – auxiliary space for the sum and count grids, plus the result grid.

Solution

The approach involves:

  1. Iterating over all potential top-left corners of 3x3 subgrids.
  2. For each subgrid, verifying that the absolute differences between all adjacent pairs (up, down, left, right) are within the threshold.
  3. If valid, computing the floor average of the 9 values.
  4. Updating two auxiliary matrices (one to sum region averages per pixel and another to count regions covering each pixel).
  5. Constructing the final result by processing each pixel: if it is covered by one or more regions, its final value is the floor of the accumulated sum divided by the count; if not, it remains unchanged.

Key data structures used include 2D arrays (or lists) for the image, sum, count, and result grids. Overlapping regions are handled by accumulating contributions for each pixel.

Code Solutions

# Python solution with detailed comments

def find_region_average(image, threshold):
    m = len(image)          # number of rows in image
    n = len(image[0])       # number of columns in image

    # Initialize matrices to store the sum of region averages and count of regions per pixel
    sum_regions = [[0] * n for _ in range(m)]
    count_regions = [[0] * n for _ in range(m)]
    
    # Directions for adjacent movement (right, down, left, up)
    adjacent_dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    # Iterate over all possible top-left corners of 3x3 subgrids
    for i in range(m - 2):
        for j in range(n - 2):
            valid = True
            # Capture the 3x3 subgrid
            subgrid = [image[i + x][j:j+3] for x in range(3)]
            
            # Check the adjacent pixel condition in the subgrid
            for x in range(3):
                for y in range(3):
                    for dx, dy in adjacent_dirs:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < 3 and 0 <= ny < 3:
                            if abs(subgrid[x][y] - subgrid[nx][ny]) > threshold:
                                valid = False
                                break
                    if not valid:
                        break
                if not valid:
                    break
                    
            # If the 3x3 subgrid qualifies as a region, compute its average (rounded down)
            if valid:
                total = sum(sum(row) for row in subgrid)
                avg = total // 9
                
                # Update each pixel in the subgrid with the region average information
                for x in range(3):
                    for y in range(3):
                        sum_regions[i + x][j + y] += avg
                        count_regions[i + x][j + y] += 1
    
    # Build the output result grid using the auxiliary matrices
    result = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if count_regions[i][j] > 0:
                result[i][j] = sum_regions[i][j] // count_regions[i][j]
            else:
                result[i][j] = image[i][j]
                
    return result

# Example usage:
if __name__ == '__main__':
    image = [[5, 6, 7, 10],
             [8, 9, 10, 10],
             [11, 12, 13, 10]]
    threshold = 3
    output = find_region_average(image, threshold)
    print(output)
← Back to All Questions