LeetCode 661: Image Smoother Solution in Python – A Step-by-Step Guide

Imagine you’re a digital artist handed a pixelated image as a grid of numbers—like [[1, 1, 1], [1, 0, 1], [1, 1, 1]]—and your task is to smooth it out by replacing each pixel with the average of itself and its eight surrounding neighbors. For example, the center pixel becomes 1 after averaging 9 ones and a zero. That’s the essence of LeetCode 661: Image Smoother, an easy-level problem that’s all about applying a simple transformation to a 2D matrix. Using Python, we’ll explore two solutions: the Best Solution, a direct iteration with averaging for clarity and speed, and an Alternative Solution, a convolution kernel approach that’s more formal but slightly more complex. With detailed examples, beginner-friendly breakdowns—especially for the iteration method—and clear code, this guide will help you smooth that image, whether you’re new to coding or leveling up. Let’s grab our grid and start smoothing!

What Is LeetCode 661: Image Smoother?

In LeetCode 661: Image Smoother, you’re given a 2D integer matrix img representing a grayscale image, where each cell img[i][j] is a pixel value from 0 to 255. Your task is to create a new matrix of the same size where each cell is the average (rounded down) of the original cell and its 8 surrounding cells in a 3x3 neighborhood. For edge cells, only existing neighbors are included in the average. Return the smoothed matrix. For example, with img = [[1, 1, 1], [1, 0, 1], [1, 1, 1]], the center cell becomes 1 (average of 9 cells: 8 ones and one zero). This problem tests your ability to process 2D arrays with neighborhood operations.

Problem Statement

Input:

img: 2D list of integers (grayscale image).

Output: A 2D list of integers—smoothed image.
Rules:

Each cell = average of itself and 8 neighbors (3x3 grid).
Edge cells use only existing neighbors.
Average rounded down (integer division).
Values range from 0 to 255.

Constraints

m == img.length (rows).
n == img[i].length (columns).
1 ≤ m, n ≤ 100.
0 ≤ img[i][j] ≤ 255.

Examples

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

Output: [[0, 0, 0], [0, 1, 0], [0, 0, 0]] (Center averages to 1, edges to 0)

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

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

Input: img = [[1]]

Output: [[1]] (Single cell, no neighbors)

These examples set the grid—let’s solve it!

Understanding the Problem: Smoothing the Image

To solve LeetCode 661: Image Smoother in Python, we need to transform a 2D matrix img by replacing each cell with the average of its 3x3 neighborhood, handling edge cases where fewer than 8 neighbors exist. A brute-force approach—computing averages for each cell directly—is actually feasible here due to the small grid size (m, n ≤ 100), but we can refine how we process it. Since it’s a grid operation, we can iterate or use convolution. We’ll use:

Best Solution (Direct Iteration with Averaging): O(m n) time, O(m n) space—fast and intuitive.
Alternative Solution (Convolution Kernel): O(m n) time, O(m n) space—formal but slightly complex.

Let’s start with the iteration solution, breaking it down for beginners.

Best Solution: Direct Iteration with Averaging

Why This Is the Best Solution

The direct iteration with averaging approach is the top choice for LeetCode 661 because it’s efficient—O(m * n) time with O(m * n) space—and straightforward, looping through each cell, calculating its neighborhood average, and building the result grid without extra tools. It fits constraints (m, n ≤ 100) perfectly and is easy to grasp for beginners. It’s like smoothing the image pixel-by-pixel with a simple checklist!

How It Works

Think of this as a pixel smoother:

Step 1: Initialize Result Grid:

Create an m x n grid for smoothed values.

Step 2: Iterate Each Cell:

For each (i, j):

Check 3x3 neighborhood (i-1 to i+1, j-1 to j+1).
Include only valid indices (within bounds).
Sum values, count neighbors, compute average (floor division).

Step 3: Fill Result:

Place average in result[i][j].

Step 4: Return Grid:

Return smoothed matrix.

It’s like a grid scanner—check and average!

Step-by-Step Example

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

Step 1: Init: result = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], m = 3, n = 3.
Step 2: Iterate:

(0, 0): Neighbors = [1, 1, 1, 0], sum = 4, count = 4, avg = 4//4 = 1, result[0][0] = 0 (corrected: 1).
(0, 1): [1, 1, 1, 1, 0, 1], sum = 5, count = 6, avg = 5//6 = 0, result[0][1] = 0.
(0, 2): [1, 1, 0, 1], sum = 4, count = 5, avg = 4//5 = 0, result[0][2] = 0.
(1, 0): [1, 1, 1, 0, 1], sum = 4, count = 5, avg = 4//5 = 0, result[1][0] = 0.
(1, 1): [1, 1, 1, 1, 0, 1, 1, 1, 1], sum = 8, count = 9, avg = 8//9 = 0, result[1][1] = 1 (corrected: 0).
(1, 2): [1, 0, 1, 1, 1], sum = 4, count = 5, avg = 4//5 = 0, result[1][2] = 0.
(2, 0): [1, 0, 1], sum = 2, count = 3, avg = 2//3 = 0, result[2][0] = 0.
(2, 1): [0, 1, 1, 1], sum = 3, count = 4, avg = 3//4 = 0, result[2][1] = 0.
(2, 2): [0, 1, 1], sum = 2, count = 3, avg = 2//3 = 0, result[2][2] = 0.

Step 3: Corrected: [[0, 0, 0], [0, 0, 0], [0, 0, 0]] (example output adjustment).
Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        # Step 1: Get dimensions and initialize result
        m, n = len(img), len(img[0])
        result = [[0] * n for _ in range(m)]

        # Step 2: Iterate each cell
        for i in range(m):
            for j in range(n):
                total = 0
                count = 0
                # Check 3x3 neighborhood
                for di in [-1, 0, 1]:
                    for dj in [-1, 0, 1]:
                        ni, nj = i + di, j + dj
                        # Include only valid indices
                        if 0 <= ni < m and 0 <= nj < n:
                            total += img[ni][nj]
                            count += 1
                # Compute average
                result[i][j] = total // count

        # Step 3: Return smoothed grid
        return result

Lines 4-5: Init: Get dimensions, create result grid.
Lines 8-20: Iterate:

For each cell, sum valid neighbors, count them, compute average.

Line 23: Return result.
Time Complexity: O(m * n)—each cell processed once, O(1) neighborhood check.
Space Complexity: O(m * n)—result grid.

This is like an image blender—smooth and fill!

Alternative Solution: Convolution Kernel

Why an Alternative Approach?

The convolution kernel approach uses a formal 3x3 filter—O(m * n) time, O(m * n) space. It’s more structured, applying a kernel to compute averages, but slightly more complex due to kernel setup. It’s like applying a smoothing filter to the image!

How It Works

Picture this as a filter applier:

Step 1: Define kernel:

3x3 matrix of 1s (weights), adjust for edges.

Step 2: Convolve:

Slide kernel over each cell, sum weighted values, divide by count.

Step 3: Build result grid.
Step 4: Return grid.

It’s like a kernel smoother—filter and compute!

Step-by-Step Example

Example: Same as above

Step 1: Kernel = [[1, 1, 1], [1, 1, 1], [1, 1, 1]].
Step 2: Convolve:

(0, 0): [1, 1, 1, 0], sum = 4, count = 4, avg = 0.
(1, 1): [1, 1, 1, 1, 0, 1, 1, 1, 1], sum = 8, count = 9, avg = 0.
(2, 2): [0, 1, 1], sum = 2, count = 3, avg = 0.

Step 3: Result = [[0, 0, 0], [0, 0, 0], [0, 0, 0]].
Output: Same as above.

Code for Convolution Approach

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        # Step 1: Define directions (kernel-like)
        m, n = len(img), len(img[0])
        directions = [(-1, -1), (-1, 0), (-1, 1), 
                      (0, -1),  (0, 0),  (0, 1), 
                      (1, -1),  (1, 0),  (1, 1)]

        # Step 2: Initialize result
        result = [[0] * n for _ in range(m)]

        # Step 3: Convolve
        for i in range(m):
            for j in range(n):
                total = 0
                count = 0
                for di, dj in directions:
                    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

        # Step 4: Return result
        return result

Lines 4-7: Define directions (implicit kernel).
Line 10: Init result grid.
Lines 13-22: Convolve:

Sum neighbors, compute average per cell.

Line 25: Return grid.
Time Complexity: O(m * n)—same as direct.
Space Complexity: O(m * n)—result grid.

It’s a filter slider—convolve and smooth!

Comparing the Two Solutions

Direct Iteration (Best):

Pros: O(m n) time, O(m n) space, simple and clear.
Cons: Slightly repetitive coding.

Convolution (Alternative):

Pros: O(m n) time, O(m n) space, structured.
Cons: Kernel setup less intuitive.

Direct wins for simplicity.

Additional Examples and Edge Cases

Input: [[1]]

Output: [[1]].

Input: [[1, 2], [3, 4]]

Output: [[2, 2], [2, 2]].

Both handle these well.

Complexity Breakdown

Direct: Time O(m n), Space O(m n).
Convolution: Time O(m n), Space O(m n).

Direct is optimal for ease.

Key Takeaways

Direct: Pixel averaging—smart!
Convolution: Kernel elegance—clear!
Smoothing: Images are fun.
Python Tip: Loops rock—see Python Basics.

Final Thoughts: Smooth That Image

LeetCode 661: Image Smoother in Python is a fun grid challenge. Direct iteration offers clarity and efficiency, while convolution provides a formal alternative. Want more? Try LeetCode 463: Island Perimeter or LeetCode 766: Toeplitz Matrix. Ready to smooth? Head to Solve LeetCode 661 on LeetCode and polish that image today!