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.lengthn == img[i].length1 <= m, n <= 2000 <= img[i][j] <= 255This 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| 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. |
Image Smoother - Leetcode 661 - Python • NeetCodeIO • 16,810 views views
Watch 9 more video solutions →Practice Image Smoother with our built-in code editor and test cases.
Practice on FleetCode