Skip to main content
Talentd

Image Smoother - Solution & Explanation

EasyArrayMatrix15 min readAsked at: Amazon, Microsoft, Apple +3
Practice this problem

Problem Statement

An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.

 

Example 1:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Example 2:

Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

 

Constraints:

  • m == img.length
  • n == img[i].length
  • 1 <= m, n <= 200
  • 0 <= img[i][j] <= 255

Approach Overview

Problem Overview: You receive a 2D matrix representing a grayscale image. For every pixel, compute the average of that pixel and all valid neighbors in its surrounding 3×3 region. Out-of-bounds neighbors are ignored, and the final value is the floor of the average.

Approach 1: Brute Force with Neighbor Validation (Time: O(m*n), Space: O(m*n))

The direct solution iterates through every cell of the matrix and inspects up to 8 surrounding neighbors plus the cell itself. For each position (i, j), loop through the relative offsets -1..1 for rows and columns to examine the 3×3 region. During the scan, check bounds to ensure the neighbor exists inside the grid before adding its value to the running sum and incrementing the count. The smoothed pixel value becomes sum // count. This method is straightforward and easy to reason about, making it ideal for interviews where correctness and clarity matter. The algorithm touches each pixel once and inspects at most 9 cells, so the total time complexity is O(m*n). The output matrix requires O(m*n) space. This approach relies heavily on simple iteration over a matrix and basic array traversal.

Approach 2: Iterative with Sliding Window Optimization (Time: O(m*n), Space: O(1) extra)

You can reduce repeated neighbor checks by treating the 3×3 neighborhood as a sliding window across each row. Instead of recomputing all surrounding values from scratch, maintain partial sums while moving horizontally. As the window shifts from column j to j+1, subtract the values leaving the left edge of the window and add the values entering from the right edge. Boundary handling still applies for the first and last columns, but most computations are reused. This reduces constant overhead and improves cache locality while keeping the same asymptotic complexity. The algorithm still processes each pixel once, so time complexity remains O(m*n), while auxiliary memory stays O(1) beyond the output grid. This pattern appears frequently in grid problems involving neighborhood aggregation in a matrix.

Recommended for interviews: Start with the brute force neighbor validation approach. It clearly demonstrates you understand how to traverse a grid and handle boundary conditions. Once that works, mention the sliding window idea to reduce repeated calculations. Interviewers usually expect the brute force implementation since its time complexity is already optimal at O(m*n), but discussing optimization shows deeper familiarity with grid processing patterns.

Approach 1: Brute Force with Neighbor Validation

This approach involves iterating over each cell and calculating the sum and count of valid neighbors in the 3x3 neighborhood range. For each cell, we consider neighboring cells that exist and are within bounds.

The solution iterates through the matrix, and for each element, it checks all possible neighbors (a total of 9 when considering the center). We keep track of sum and count to calculate the average for valid neighbors. Floor function is used to compute the rounded down result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(m * n * 9), which simplifies to O(m * n) because we are only performing a fixed amount of work per cell. The space complexity is O(m * n) for storing the result matrix.

Try this approach in the editor →

Approach 2: Iterative with Sliding Window Optimization

This approach leverages a sliding window technique within the 3x3 area, minimizing redundant calculations by reusing previously computed sums and counts from prior cells wherever applicable.

Unfortunately, a C implementation using a sophisticated sliding window for this problem context is not readily available.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time and space complexities remain as O(m * n) due to the sliding optimization remaining bounded per cell, though potentially with reduced constant factor.

Try this approach in the editor →

Approach 3: Direct Traversal

We create a 2D array ans of size m times n, where ans[i][j] represents the smoothed value of the cell in the i-th row and j-th column of the image.

For ans[i][j], we traverse the cell in the i-th row and j-th column of img and its surrounding 8 cells, calculate their sum s and count cnt, then compute the average value s / cnt and store it in ans[i][j].

After the traversal, we return ans.

The time complexity is O(m times n), where m and n are the number of rows and columns of img, respectively. Ignoring the space consumption of the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Neighbor Validation

The time complexity is O(m * n * 9), which simplifies to O(m * n) because we are only performing a fixed amount of work per cell. The space complexity is O(m * n) for storing the result matrix.

Iterative with Sliding Window Optimization

The time and space complexities remain as O(m * n) due to the sliding optimization remaining bounded per cell, though potentially with reduced constant factor.

Direct Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Neighbor ValidationO(m*n)O(m*n)Best for interviews and clarity. Simple implementation that directly checks the 3×3 neighborhood.
Iterative Sliding Window OptimizationO(m*n)O(1) extraUseful when minimizing repeated calculations across adjacent columns or improving cache efficiency.

Video Solution

Image Smoother - Leetcode 661 - Python • NeetCodeIO • 18,389 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Image Smoother easy or hard?
Image Smoother is classified as an Easy problem. The challenge lies mainly in correctly handling matrix boundaries and computing the average of valid neighbors without accessing invalid indices.
Image Smoother Python/Java solution
The typical implementation loops through each cell, checks the 3x3 surrounding area using two nested loops, validates boundaries, and computes the integer average. The same logic works across Python, Java, C++, and JavaScript with identical O(m*n) complexity.
How to solve Image Smoother in O(n)?
For a matrix with m rows and n columns, the optimal solution is O(m*n). Each pixel must be visited to compute its smoothed value. Using a sliding window technique can reduce repeated neighbor calculations but does not change the asymptotic complexity.
What is the best approach for Image Smoother?
The standard approach iterates through every cell and averages values in its surrounding 3x3 neighborhood while skipping out-of-bounds indices. This brute force neighbor validation method runs in O(m*n) time and is already optimal because each pixel must be processed at least once.
Is Image Smoother asked at Google/Amazon/Meta?
Matrix traversal and neighborhood aggregation problems like Image Smoother commonly appear in interviews at companies such as Amazon and Google. They test boundary handling, grid traversal, and careful iteration logic rather than advanced algorithms.
What data structure is used in Image Smoother?
The problem primarily uses a 2D array (matrix). The algorithm iterates through the grid and inspects adjacent cells using simple index offsets. No advanced data structures are required.
What is the time complexity of Image Smoother?
The time complexity is O(m*n), where m and n are the matrix dimensions. Each cell checks up to 9 positions in its 3x3 neighborhood, which is a constant factor. Space complexity is O(m*n) for the output matrix.

Ready to solve this problem?

Practice Image Smoother with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays