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

Image Smoother

Difficulty: Easy

Problem Description

An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells. Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.

Key Insights

  • The smoothing process involves averaging the current cell and its neighbors.
  • The average should only include existing neighbors (i.e., cells within bounds).
  • The result for each cell is the floor of the calculated average.
  • Edge and corner cells have fewer neighbors, which must be handled appropriately.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the image. Each cell is processed exactly once. Space Complexity: O(m * n) for the output array, which stores the smoothed image.

Solution

To solve this problem, we will iterate through each cell in the input image. For each cell, we will calculate the sum of the values of the cell and its valid neighbors (those within the matrix bounds). We will keep track of the count of valid neighbors to compute the average. Finally, we will round down the average using integer division and store the result in a new matrix which will represent the smoothed image.

We will utilize a simple nested loop to traverse the image and a separate list to hold the results so that we do not modify the input while calculating the output.

Code Solutions

def imageSmoother(img):
    m, n = len(img), len(img[0])
    result = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j in range(n):
            total = 0
            count = 0
            
            # Check all 9 neighboring cells
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if 0 <= x < m and 0 <= y < n:
                        total += img[x][y]
                        count += 1
            
            # Calculate the floored average
            result[i][j] = total // count
    
    return result
← Back to All Questions