#661

Easy

LeetCode Problem Workspace

Image Smoother

Apply a 3x3 smoothing filter to a matrix, rounding down each cell average including surrounding neighbors for accurate results.

array matrix

Problem Statement

Given an m x n integer matrix representing the grayscale of an image, implement a smoothing operation where each cell is replaced by the floor of the average of itself and all valid surrounding cells within a 3x3 window.

Cells on the edge or corner of the matrix have fewer neighbors; only include existing cells in the averaging. Return the resulting matrix after applying this image smoother to every cell.

Examples

Example 1

Input: img = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[0,0,0],[0,0,0],[0,0,0]]

For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Example 2

Input: img = [[100,200,100],[200,50,200],[100,200,100]]

Output: [[137,141,137],[141,138,141],[137,141,137]]

For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137 For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141 For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

Constraints

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

Solution Approach

Iterate with Neighbor Offsets

For each cell, use nested loops to consider all 8 surrounding positions plus the cell itself. Check boundaries to include only valid neighbors and compute the sum and count for averaging.

Compute Floor Average

After summing all valid neighboring values, divide by the count of included cells and apply floor operation. Assign this value to the corresponding position in the result matrix.

Optimize Space Usage

Either update a new matrix to store results or use in-place marking techniques to avoid extra O(m*n) space. This ensures the algorithm stays efficient for large images without overwriting values prematurely.

Complexity Analysis

Metric	Value
Time	O(m \cdot n)
Space	O(1)

Time complexity is O(m * n) because each cell is visited once and up to 9 neighbors are checked. Space complexity is O(1) if using in-place updates or auxiliary constant space for neighbor sum, otherwise O(m * n) for a separate result matrix.

What Interviewers Usually Probe

You might be asked about boundary handling and why neighbors count varies.
Expect clarifications on floor vs. rounding behavior for averages.
The interviewer may probe about in-place updates versus using extra space.

Common Pitfalls or Variants

Common pitfalls

Failing to handle corner and edge cells correctly.
Overwriting original matrix before computing all averages.
Miscounting neighbors leading to incorrect floor division results.

Follow-up variants

Use different kernel sizes such as 5x5 smoothing filter.
Compute weighted averages giving the center cell higher weight.
Apply smoothing repeatedly for multiple passes on the same matrix.

FAQ

What is the main challenge in Image Smoother on LeetCode?

The main challenge is handling edge and corner cells correctly while computing the floor average with neighbors in the 3x3 window.

Can Image Smoother be solved in-place?

Yes, but care must be taken to avoid overwriting values needed for other cells; using markers or a separate matrix is safer.

Why is floor used instead of normal rounding?

The problem specifies floor to ensure consistent truncation of the average, which affects the expected output exactly as in examples.

What pattern does Image Smoother represent?

It is an Array plus Matrix pattern, combining iteration over a matrix with neighbor-based calculations for each cell.

What are common mistakes when implementing this smoother?

Common mistakes include miscounting neighbors, ignoring boundaries, and updating the original matrix too early, leading to wrong averages.

terminal

Solution

Solution 1: Direct Traversal

We create a 2D array $\textit{ans}$ of size $m \times n$, where $\textit{ans}[i][j]$ represents the smoothed value of the cell in the $i$-th row and $j$-th column of the image.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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):
                s = cnt = 0
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n:
                            cnt += 1
                            s += img[x][y]
                ans[i][j] = s // cnt
        return ans

Continue Practicing

#675 cut off trees for golf event #695 max area of island #733 flood fill