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.

Description Solution Video 16:02

661. Image Smoother

Easy69.8% acceptance6 companies

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

Asked at 6 companies

Visa Amazon Roblox Microsoft Apple Meta

Topics

Array Matrix

16:02

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[[100,200,100],[200,50,200],[100,200,100]]

Your code is saved on this device.Solution