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
Mwhere 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
-
Preprocessing:
- Create a new matrix
cumulative_sumwhere 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.
- Create a new matrix
-
Smoothing:
- Create a new matrix
resultto 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.
- Create a new matrix
-
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.