LeetCode 661: Image Smoother

Problem Restatement

We are given a grayscale image represented as a 2D integer matrix img.

Each cell contains a pixel value.

We must create a smoothed image.

For every cell, compute the average of:

1. The cell itself
2. All valid neighboring cells

Neighbors include all eight surrounding directions:

top
bottom
left
right
top-left
top-right
bottom-left
bottom-right

The average is rounded down to the nearest integer.

Cells outside the image boundaries are ignored.

Return the resulting smoothed matrix.

Input and Output

Example function shape:

def imageSmoother(img: list[list[int]]) -> list[list[int]]:
    ...

Examples

Consider:

img = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
]

For the center cell:

0

we average all 9 cells:

1 + 1 + 1
1 + 0 + 1
1 + 1 + 1

The sum is:

8

The count is:

9

So:

8 // 9 = 0

For the top-left corner:

1

only 4 cells are valid:

1 1
1 0

The sum is:

3

The count is:

4

So:

3 // 4 = 0

The final output is:

[
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
]

Another example:

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

The smoothed image becomes:

[
    [137, 141, 137],
    [141, 138, 141],
    [137, 141, 137],
]

First Thought: Direct Simulation

For every cell, we can check all neighboring positions.

There are only:

9 possible positions

including the cell itself.

So for each cell:

1. Visit all neighboring offsets.
2. Ignore positions outside the matrix.
3. Compute the total sum.
4. Count how many cells were included.
5. Store:

sum // count

This is efficient because each cell only checks a constant number of neighbors.

Key Insight

The important detail is boundary handling.

For a middle cell, all 9 surrounding positions exist.

For an edge or corner cell, some neighbors fall outside the matrix and must be ignored.

So before using a neighbor position:

(nr, nc)

we must verify:

0 <= nr < rows
0 <= nc < cols

Direction Offsets

We can represent all neighboring positions using row and column offsets.

The offsets are:

For a cell:

(r, c)

the neighbor becomes:

(r + dr, c + dc)

Algorithm

1. Get matrix dimensions.
2. Create an output matrix.
3. For every cell:
   • Initialize total = 0
   • Initialize count = 0
4. Check all 9 neighboring offsets.
5. If the neighbor is inside bounds:
   • Add its value to total
   • Increase count
6. Store:

total // count

in the result matrix.

7. Return the result.

Correctness

For each cell (r, c), the algorithm examines every possible neighboring position, including the cell itself.

A neighboring position is included only if it lies inside the matrix boundaries. Therefore, the algorithm includes exactly the valid neighbors required by the problem.

The variables total and count accumulate:

The algorithm stores:

total // count

which is exactly the floor of the average required by the problem statement.

Since this process is applied independently to every cell, the resulting matrix is the correctly smoothed image.

Complexity

The neighbor loop is constant size, so it does not affect asymptotic complexity.

Implementation

from typing import List

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        rows = len(img)
        cols = len(img[0])

        result = [[0] * cols for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                total = 0
                count = 0

                for dr in (-1, 0, 1):
                    for dc in (-1, 0, 1):
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < rows and 0 <= nc < cols:
                            total += img[nr][nc]
                            count += 1

                result[r][c] = total // count

        return result

Code Explanation

We first compute the matrix dimensions:

rows = len(img)
cols = len(img[0])

Then create the output matrix:

result = [[0] * cols for _ in range(rows)]

We process every cell:

for r in range(rows):
    for c in range(cols):

For each cell, we track:

total = 0
count = 0

Then we check all neighboring offsets:

for dr in (-1, 0, 1):
    for dc in (-1, 0, 1):

The neighbor position becomes:

nr = r + dr
nc = c + dc

We only use neighbors inside the image:

if 0 <= nr < rows and 0 <= nc < cols:

Then we update the running sum and count:

total += img[nr][nc]
count += 1

Finally, we compute the floor average:

result[r][c] = total // count

After all cells are processed, we return the smoothed image.

Testing

def run_tests():
    s = Solution()

    img = [
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ]

    assert s.imageSmoother(img) == [
        [0, 0, 0],
        [0, 0, 0],
        [0, 0, 0],
    ]

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

    assert s.imageSmoother(img) == [
        [137, 141, 137],
        [141, 138, 141],
        [137, 141, 137],
    ]

    img = [
        [5],
    ]

    assert s.imageSmoother(img) == [
        [5],
    ]

    img = [
        [1, 2],
        [3, 4],
    ]

    assert s.imageSmoother(img) == [
        [2, 2],
        [2, 2],
    ]

    print("all tests passed")

run_tests()

Test meaning: