LeetCode 661 - Image Smoother

The problem is asking us to implement an image smoother, a filter that modifies each cell in a 2D grayscale image based on the average of itself and its surrounding cells in a 3 x 3 window.

leetcodeeasyarraymatrix

LeetCode Problem 661

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem is asking us to implement an image smoother, a filter that modifies each cell in a 2D grayscale image based on the average of itself and its surrounding cells in a 3 x 3 window. The key requirement is that we only consider the neighboring cells that exist; for edge or corner cells, the number of neighbors will be fewer than eight. The output is a matrix of the same size as the input, where each cell has been replaced by the floor of the average of its neighbors and itself.

The input, img, is an m x n matrix where each element is an integer between 0 and 255 representing grayscale intensity. The output must also be an m x n integer matrix. The constraints indicate that the matrix can be relatively small (1 <= m, n <= 200), so we can afford an algorithm that iterates over each cell and its neighbors without hitting performance issues. Important edge cases include the smallest images (1x1, 1xN, Mx1) and cells on the edges or corners of the matrix, where fewer neighbors exist.

Approaches

The brute-force approach is straightforward: for each cell, manually iterate over the 3x3 window centered on that cell, sum up all valid neighbor values, count how many valid neighbors there are, and compute the integer division (floor) of the sum by the count. This approach works correctly because it directly follows the problem statement, but it requires nested loops over the matrix and the 3x3 window, resulting in potentially redundant computation.

The optimal approach improves on this by recognizing that although we still need to access each cell's neighbors, the computational complexity is already acceptable given the problem constraints (O(m * n)), and the problem size (200x200) is small. Therefore, a simple brute-force iteration with careful boundary checking is already efficient enough for this problem. Additional optimizations, such as precomputing prefix sums, are unnecessary for this scale.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n) Iterate through each cell and its neighbors, compute average
Optimal O(m * n) O(m * n) Same as brute force, boundary checking ensures correctness

Algorithm Walkthrough

  1. Initialize a result matrix res of the same dimensions as the input matrix img.
  2. Iterate over each row i and column j of img.
  3. For each cell (i, j), initialize total_sum to 0 and count to 0. These will track the sum of valid neighbor values and their count.
  4. Iterate over the relative neighbor positions dx and dy in [-1, 0, 1].
  5. For each neighbor, compute ni = i + dx and nj = j + dy. Check if (ni, nj) lies within the matrix boundaries. If valid, add img[ni][nj] to total_sum and increment count.
  6. After processing all neighbors, compute the floored average as floor(total_sum / count) and assign it to res[i][j].
  7. Continue until all cells have been processed.
  8. Return res.

Why it works: Each cell considers exactly the neighbors that exist, and by summing and counting these neighbors, we correctly compute the floored average. The approach guarantees correctness because it directly follows the problem specification, including boundary handling for edges and corners.

Python Solution

from typing import List

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        res = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                total_sum = 0
                count = 0
                for dx in [-1, 0, 1]:
                    for dy in [-1, 0, 1]:
                        ni, nj = i + dx, j + dy
                        if 0 <= ni < m and 0 <= nj < n:
                            total_sum += img[ni][nj]
                            count += 1
                res[i][j] = total_sum // count
        
        return res

The Python implementation first initializes the result matrix with zeros. It then loops over each cell, sums the valid neighbors, counts them, and stores the integer division into the result matrix. Boundary checks ensure that edge and corner cells are correctly averaged without indexing errors.

Go Solution

func imageSmoother(img [][]int) [][]int {
    m, n := len(img), len(img[0])
    res := make([][]int, m)
    for i := 0; i < m; i++ {
        res[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            totalSum := 0
            count := 0
            for dx := -1; dx <= 1; dx++ {
                for dy := -1; dy <= 1; dy++ {
                    ni, nj := i + dx, j + dy
                    if ni >= 0 && ni < m && nj >= 0 && nj < n {
                        totalSum += img[ni][nj]
                        count++
                    }
                }
            }
            res[i][j] = totalSum / count
        }
    }

    return res
}

In Go, slices are initialized using make, and the same nested loop logic is applied. Integer division automatically floors the result. Boundary checks ensure no out-of-range access occurs.

Worked Examples

Example 1:

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

i j Neighbors Sum Count Average
0 0 1,1,1,0 3 4 0
0 1 1,1,1,1,0 4 5 0
1 1 all 9 cells 8 9 0

Resulting matrix: [[0,0,0],[0,0,0],[0,0,0]]

Example 2:

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

i j Neighbors Sum Count Average
0 0 100,200,200,50 550 4 137
1 1 all 9 cells 1250 9 138

Resulting matrix: [[137,141,137],[141,138,141],[137,141,137]]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited once, and we check up to 9 neighbors per cell, which is constant.
Space O(m * n) We create a separate matrix of the same size as input for the result.

The algorithm scales linearly with the number of cells in the matrix, and the 3x3 neighborhood checking does not increase asymptotic complexity since it is a fixed size.

Test Cases

# Provided examples
assert Solution().imageSmoother([[1,1,1],[1,0,1],[1,1,1]]) == [[0,0,0],[0,0,0],[0,0,0]]  # basic 3x3 with center zero
assert Solution().imageSmoother([[100,200,100],[200,50,200],[100,200,100]]) == [[137,141,137],[141,138,141],[137,141,137]]  # larger values

# Edge cases
assert Solution().imageSmoother([[1]]) == [[1]]  # single element
assert Solution().imageSmoother([[1,2,3]]) == [[1,2,2]]  # single row
assert Solution().imageSmoother([[1],[2],[3]]) == [[1],[2],[2]]  # single column

# All same values
assert Solution().imageSmoother([[5,5],[5,5]]) == [[5,5],[5,5]]  # uniform matrix

# Maximum size small test
img = [[255]*5 for _ in range(5)]
assert Solution().imageSmoother(img) == [[255]*5 for _ in range(5]]  # uniform max intensity
Test Why
3x3 with zero center Tests floor and neighbor counting
3x3 larger values Tests integer division correctness
1x1 matrix Single cell edge case
1xN and Nx1 Single row and column edge cases
Uniform values Ensures averaging preserves value
Maximum intensity Tests upper boundary of pixel values

Edge Cases

One important edge case is a 1x1 matrix. There is only one cell, so the smoothed value is the cell itself