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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Grid of Region Average

Difficulty: Medium

Problem Description

You are given a 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.

Key Insights

  • A region is defined as a 3x3 subgrid with the condition on intensity differences between adjacent pixels.
  • Each pixel can be part of multiple regions, and the result for each pixel depends on the averages of those regions.
  • The averaging process requires careful handling of rounding down values.

Space and Time Complexity

Time Complexity: O(m * n) - We need to examine each pixel and its neighbors. Space Complexity: O(m * n) - We maintain a result grid of the same size as the input image.

Solution

To solve this problem, we will use a breadth-first search (BFS) or depth-first search (DFS) approach to identify regions in the image. We will iterate over each pixel and, whenever we find a pixel that can be the starting point of a region (based on the threshold), we will explore the entire region and calculate the average intensity. We will use a queue (for BFS) or a stack (for DFS) to keep track of the pixels we need to explore. After identifying all regions, we will calculate the average intensity for each pixel based on the regions it belongs to. Finally, we will return the result grid.

Code Solutions

def findRegionAverage(image, threshold):
    from collections import deque
    m, n = len(image), len(image[0])
    result = [[0] * n for _ in range(m)]
    visited = [[False] * n for _ in range(m)]
    
    def is_valid(x, y):
        return 0 <= x < m and 0 <= y < n

    def bfs(i, j):
        queue = deque([(i, j)])
        visited[i][j] = True
        region_sum = 0
        region_count = 0
        region_pixels = [(i, j)]
        
        while queue:
            x, y = queue.popleft()
            region_sum += image[x][y]
            region_count += 1
            
            # Check adjacent pixels
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if is_valid(nx, ny) and not visited[nx][ny]:
                    if abs(image[x][y] - image[nx][ny]) <= threshold:
                        visited[nx][ny] = True
                        queue.append((nx, ny))
                        region_pixels.append((nx, ny))
        
        region_avg = region_sum // region_count
        return region_avg, region_pixels

    region_averages = {}
    
    for i in range(m):
        for j in range(n):
            if not visited[i][j]:
                region_avg, region_pixels = bfs(i, j)
                for x, y in region_pixels:
                    if (x, y) not in region_averages:
                        region_averages[(x, y)] = []
                    region_averages[(x, y)].append(region_avg)

    for i in range(m):
        for j in range(n):
            if (i, j) in region_averages:
                result[i][j] = sum(region_averages[(i, j)]) // len(region_averages[(i, j)])
            else:
                result[i][j] = image[i][j]

    return result
← Back to All Questions