Domain 1EasyCORE

Image Smoother

The problem requires us to smooth out the grayscale values in a given 2D matrix. Each cell's new value should be the average of its own value and the values of all surrounding cells (up to 8 neighbors). If a cell is on the edge or corner, it will have fewer than 8 neighbors. The averaging should round down to the nearest integer.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

661. Image Smoother

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.4%


Problem Breakdown

The problem requires us to smooth out the grayscale values in a given 2D matrix. Each cell’s new value should be the average of its own value and the values of all surrounding cells (up to 8 neighbors). If a cell is on the edge or corner, it will have fewer than 8 neighbors. The averaging should round down to the nearest integer.

Inputs:

  • A 2D matrix M where each element represents the grayscale value of an image pixel.

Outputs:

  • A new 2D matrix where each element is the smoothed grayscale value.

Implicit Constraints or Tricky Edge Cases:

  • The matrix can be as small as 1x1.
  • Cells on the border and corners have fewer than 8 neighbors.
  • Values are in the range [0, 255].

Intuition

A brute-force approach would involve iterating over each cell, checking all possible neighboring cells, summing their values, and then dividing by the number of valid neighbors. This approach is inefficient because it involves multiple nested loops and repeated checks for neighbor validity.

The key insight is to avoid recalculating the sum of neighbors for each cell. Instead, we can preprocess the matrix to store cumulative sums in a new matrix. Then, when calculating the average for each cell, we can use these cumulative sums to quickly determine the total and count of valid neighbors.

Approach

  1. Preprocessing:

    • Create a new matrix cumulative_sum where each element at position (i, j) stores the sum of all elements in the submatrix from (0, 0) to (i, j).
    • Iterate through the original matrix and fill in the cumulative sums.
  2. Smoothing:

    • Create a new matrix result to store the smoothed values.
    • For each cell (i, j):
      • Determine the bounds of the submatrix that includes all valid neighbors.
      • Use the cumulative sum matrix to quickly calculate the total sum and count of valid neighbors.
      • Compute the average by dividing the total sum by the count of valid neighbors.
  3. Edge Cases:

    • Handle cells on the border and corners by adjusting the bounds of the submatrix.

Complexity Analysis

  • Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the matrix. This is because we iterate through the matrix twice (once for preprocessing, once for smoothing).
  • Space Complexity: O(n*m) due to the additional cumulative sum matrix.

Solution

def imageSmoother(M):
    if not M or not M[0]:
        return []
    
    n, m = len(M), len(M[0])
    cumulative_sum = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Preprocess to create cumulative sum matrix
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cumulative_sum[i][j] = M[i-1][j-1] + cumulative_sum[i-1][j] + cumulative_sum[i][j-1] - cumulative_sum[i-1][j-1]
    
    result = [[0] * m for _ in range(n)]
    
    # Calculate the smoothed values
    for i in range(n):
        for j in range(m):
            row_start, col_start = max(0, i-1), max(0, j-1)
            row_end, col_end = min(n-1, i+1), min(m-1, j+1)
            
            total_sum = cumulative_sum[row_end + 1][col_end + 1] - cumulative_sum[row_start][col_end + 1] - cumulative_sum[row_end + 1][col_start] + cumulative_sum[row_start][col_start]
            count = (row_end - row_start + 1) * (col_end - col_start + 1)
            
            result[i][j] = total_sum // count
    
    return result

Edge Cases Handled

  • Empty Matrix: The function returns an empty matrix if the input is empty.
  • Single Cell Matrix: Handles a 1x1 matrix correctly by returning the same value.
  • Border and Corner Cells: Adjusts the bounds of the submatrix to include only valid neighbors.