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

Image Smoother

Number: 661

Difficulty: Easy

Paid? No

Companies: Amazon, Visa, Bloomberg

Problem Description

Given an m x n integer matrix representing a grayscale image, modify the matrix so that each cell's new value is the floor of the average of its own value and those of its surrounding 8 neighbors (if they exist). For cells on the border or corners, only the available neighbors are considered.

Key Insights

  • Iterate over each cell in the matrix.
  • For every cell, examine all potential neighbors using a 3x3 grid centered on the cell.
  • Check boundaries to avoid accessing indexes out of range.
  • Sum the values of the valid neighbors and compute the floor of the average using integer division.
  • Use an auxiliary matrix to store the results to avoid interference with ongoing computation.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the matrix (since each cell is processed and each cell processes at most 9 elements). Space Complexity: O(m * n) for the auxiliary matrix used to store the results.

Solution

The solution involves a double-loop to traverse every cell in the input matrix. For each cell, an inner loop iterates over the 3x3 block centered at that cell. We check if the indices are within bounds before accumulating the sum and count of the valid neighbors. The new value for the cell is computed as the integer division of the sum by the count (which is equivalent to floor division). By using a separate matrix for the results, we ensure that updates do not affect the calculations for neighboring cells.

Code Solutions

# Define a function that takes an image (matrix) as input and returns the smoothed image.
def imageSmoother(img):
    # Get the dimensions of the image
    m, n = len(img), len(img[0])
    # Create a result matrix with the same dimensions initialized to zeros
    result = [[0] * n for _ in range(m)]
    
    # Loop over each cell in the image
    for i in range(m):
        for j in range(n):
            sum_val = 0  # Sum of pixel values
            count = 0    # Number of valid neighboring pixels
            
            # Iterate over the 3x3 grid centered at (i, j)
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    ni, nj = i + di, j + dj  # Neighbor indices
                    # Check if the neighbor indices are within bounds
                    if 0 <= ni < m and 0 <= nj < n:
                        sum_val += img[ni][nj]
                        count += 1
            
            # Set the smoothed value (floor division in Python)
            result[i][j] = sum_val // count
    
    return result

# Example usage:
# img = [[1,1,1],[1,0,1],[1,1,1]]
# print(imageSmoother(img))
← Back to All Questions