Image Smoother

Difficulty: Easy | Acceptance: 69.30% | Paid: No Topics: Array, Matrix

An image smoother is a filter of the size 3 x 3 that is applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., average of the nine cells in the blue smoother). If one or more of the surrounding cells does not exist, we do not consider it in the average (i.e., the average of the existing 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.

• Examples
• Constraints
• Approach 1: Simulation with Copy Matrix
• Approach 2: In-place Calculation

Examples

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the point (0,0), (0,2), (2,0) and (2,2): floor(3/4) = floor(0.75) = 0
For the point (0,1), (1,0), (1,2) and (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Explanation:
For the point (0,0), (0,2), (2,0) and (2,2): floor(100+200+200+50+100+200+100+200+100 / 9) = floor(1500 / 9) = floor(166.666667) = 166
Wait, the example calculation in the problem description is slightly different based on neighbors.
Let's re-verify the example logic provided by LeetCode.
(0,0) neighbors: (0,0), (0,1), (1,0), (1,1). Sum = 100+200+200+50 = 550. Count = 4. Avg = 137.
(0,1) neighbors: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2). Sum = 100+200+100+200+50+200 = 850. Count = 6. Avg = 141.
(1,1) neighbors: all 9. Sum = 100+200+100+200+50+200+100+200+100 = 1250. Count = 9. Avg = 138.
The output matches the logic.

Constraints

m == img.length
n == img[i].length
1 <= m, n <= 200
0 <= img[i][j] <= 255

Approach 1: Simulation with Copy Matrix

Intuition Create a new matrix to store the result. For each cell in the original matrix, iterate through its valid neighbors (including itself), sum their values, count them, and calculate the floor of the average.

Steps

• Initialize a result matrix ans with the same dimensions as img.
• Iterate through each cell (i, j) in img.
• Initialize sum and count to 0.
• Iterate through the 3x3 grid centered at (i, j) using offsets r from i-1 to i+1 and c from j-1 to j+1.
• Check if (r, c) is within bounds.
• If valid, add img[r][c] to sum and increment count.
• Store Math.floor(sum / count) in ans[i][j].
• Return ans.

from typing import List

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        ans = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                total = 0
                count = 0
                for r in range(i - 1, i + 2):
                    for c in range(j - 1, j + 2):
                        if 0 <= r < m and 0 <= c < n:
                            total += img[r][c]
                            count += 1
                ans[i][j] = total // count
        return ans

Complexity

• Time: O(mn) where m is the number of rows and n is the number of columns. We process each cell and check up to 9 neighbors.
• Space: O(mn) to store the result matrix.
• Notes: This is the most straightforward approach and is easy to understand.

Approach 2: In-place Calculation

Intuition Since the pixel values are limited to 0-255 (8 bits), we can store the new calculated value in the higher bits of the integer (e.g., bits 8-15) while keeping the original value in the lower bits (0-7). This allows us to compute the average using original values without allocating extra space for a separate matrix.

Steps

• Iterate through each cell (i, j) in img.
• Calculate the sum and count of neighbors using the original values (which are in the lower 8 bits, accessible via img[r][c] & 255).
• Compute the average and store it in the higher bits: img[i][j] |= (average << 8).
• After processing all cells, iterate through the matrix again.
• Shift each value right by 8 bits to retrieve the calculated average and overwrite the cell.

from typing import List

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        
        for i in range(m):
            for j in range(n):
                total = 0
                count = 0
                for r in range(i - 1, i + 2):
                    for c in range(j - 1, j + 2):
                        if 0 <= r < m and 0 <= c < n:
                            total += img[r][c] & 255
                            count += 1
                img[i][j] |= (total // count) << 8
        
        for i in range(m):
            for j in range(n):
                img[i][j] >>= 8
                
        return img

Complexity

• Time: O(mn) where m is the number of rows and n is the number of columns.
• Space: O(1) extra space, modifying the input matrix in-place.
• Notes: This approach optimizes space complexity by utilizing bit manipulation, which is useful when memory is constrained.