Image Smoother: Neighbor Averaging

LeetCode 661: Image Smoother gives you an m x n integer matrix representing a grayscale image. For every cell, you need to replace its value with the floor of the average of all the values in its 3x3 neighborhood, including the cell itself. Cells on the edges or corners simply have fewer neighbors to average.

The problem

You are given a 2D matrix img. For each cell (i, j), look at every cell in the surrounding 3x3 window that falls within the matrix bounds. Sum those values, count how many valid cells there are, and set the result to floor(sum / count). Return the new matrix.

For example, with input [[1,1,1],[1,0,1],[1,1,1]], the center cell has all 9 cells in its window. The sum is 8 and the count is 9, so the smoothed value is floor(8/9) = 0. Corner cells have only 4 valid neighbors, edge cells have 6, and the center has 9.

Why neighbor averaging works

Image smoothing is a fundamental operation in image processing. By replacing each pixel with the average of its local neighborhood, you blur sharp transitions and reduce noise. This is essentially a box filter, one of the simplest convolution kernels.

The key insight for solving this problem is that you do not need to handle corners, edges, and interior cells with separate logic. Instead, you iterate over all possible offsets in the range [-1, 0, 1] for both row and column directions, check whether the resulting position is in bounds, and accumulate the sum and count. This single loop handles every case uniformly.

Step-by-step walkthrough

The code

def imageSmoother(img: list[list[int]]) -> list[list[int]]:
    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
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n:
                        total += img[ni][nj]
                        count += 1
            result[i][j] = total // count
    return result

The outer loops visit every cell in the matrix. For each cell, the inner loops scan the 3x3 window using offsets from -1 to 1 in both directions. The bounds check 0 <= ni < m and 0 <= nj < n naturally handles corners and edges by skipping positions that fall outside the matrix. After summing all valid neighbor values, floor division by the count gives the smoothed result.

Complexity analysis

Time: You visit each of the m * n cells exactly once. For each cell, you check at most 9 positions in the 3x3 window. Since 9 is a constant, the per-cell work is O(1), making the total O(m * n).

Space: The result matrix requires O(m * n) extra space. You cannot avoid this because the problem asks you to return a new matrix, and smoothing in place would corrupt neighbor values that have not been processed yet.

The building blocks

Neighbor scanning in a grid

The double loop over di and dj in range(-1, 2) is a pattern you will see in many grid problems. It generates all 9 cells in a 3x3 window centered on (i, j). Combined with a bounds check, it handles every edge case without branching.

for di in range(-1, 2):
    for dj in range(-1, 2):
        ni, nj = i + di, j + dj
        if 0 <= ni < m and 0 <= nj < n:
            # process neighbor at (ni, nj)

This same pattern appears in Game of Life (counting live neighbors), minesweeper (counting adjacent mines), and flood fill (exploring adjacent cells). Once you internalize this loop structure, any problem that says "look at surrounding cells" becomes mechanical.

Edge cases

• 1x1 matrix: The single cell has no neighbors. Its smoothed value is just floor(val / 1) = val. The output equals the input.
• Single row or single column: Each cell has at most 3 neighbors (itself plus up to 2 adjacent cells in the row or column). The formula still works because the bounds check naturally excludes invalid positions.
• All identical values: If every cell contains the same value v, the average of any neighborhood is v, so the output equals the input.
• Maximum values: Cell values can be up to 255 (grayscale). The maximum sum in a 3x3 window is 255 * 9 = 2295, which fits comfortably in a standard integer. No overflow concerns.

From understanding to recall

The algorithm here is simple, but the implementation details matter. Did you remember to include the cell itself in the count? Did you write to a separate result matrix instead of modifying the input? Did you use // for floor division? These small details are easy to forget under time pressure.

The fix is practice. Write the solution from scratch: the four nested loops, the bounds check, the sum and count, the floor division. Do it today, then again in two days, then again in five. After a few repetitions, the neighbor-scanning pattern becomes automatic. You see "average of neighbors" and the di, dj loop just flows out.

Neighbor scanning is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and reinforcing them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Game of Life - Uses the same 3x3 neighbor scanning pattern, but with in-place state encoding instead of a separate output matrix
• Set Matrix Zeroes - Another matrix modification problem where you need to be careful about the order of reads and writes
• Reshape the Matrix - A different matrix traversal problem that builds intuition for row-major indexing

Once you have the neighbor-scanning pattern down, try applying it to other grid problems. The loop structure is always the same. Only the logic inside the bounds check changes.