661. Image Smoother - Explanation

1. Iteration (Using Extra Matrix)

Intuition

For each cell, we need to compute the average of all valid neighbors (including itself) within a 3x3 window.
We check all 9 potential neighbors, skip those outside the matrix bounds, sum the valid values, and divide by the count.
Since we need the original values to compute neighbors, we store results in a separate matrix.

Algorithm

Create a result matrix of the same dimensions.
For each cell (r, c), iterate through the 3x3 window centered at that cell.
For each position (i, j) in the window, check if it is within bounds.
If valid, add the value to the total and increment the count.
Set the result cell to total / count (integer division).
Return the result matrix.

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(img), len(img[0])
        res = [[0] * COLS for _ in range(ROWS)]

        for r in range(ROWS):
            for c in range(COLS):
                total, cnt = 0, 0
                for i in range(r - 1, r + 2):
                    for j in range(c - 1, c + 2):
                        if 0 <= i < ROWS and 0 <= j < COLS:
                            total += img[i][j]
                            cnt += 1
                res[r][c] = total // cnt

        return res

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n * m)$

Where $n$ is the number of rows and $m$ is the number of columns of the matrix.

2. Iteration (Using Extra Row)

Intuition

We can reduce space by only keeping track of the previous row's original values.
As we process row by row, we modify cells in place.
For neighbors in the current row, we use a copy saved before modification.
For the previous row, we use the saved copy.
For the next row, we use the original matrix values (not yet modified).

Algorithm

Save a copy of the first row as prevRow.
For each row, save a copy of the current row as currRow before processing.
For each cell, compute the average using: prevRow for the row above, currRow for the current row, and the original matrix for the row below.
Update the cell in place with the computed average.
After processing the row, set prevRow = currRow for the next iteration.
Return the modified matrix.

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(img), len(img[0])
        prev_row = img[0][:]

        for r in range(ROWS):
            curr_row = img[r][:]

            for c in range(COLS):
                total, cnt = 0, 0
                for i in range(max(0, r - 1), min(ROWS, r + 2)):
                    for j in range(max(0, c - 1), min(COLS, c + 2)):
                        if i == r:
                            total += curr_row[j]
                        elif i == r - 1:
                            total += prev_row[j]
                        else:
                            total += img[i][j]
                        cnt += 1
                img[r][c] = total // cnt

            prev_row = curr_row

        return img

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$ extra space.

Where $n$ is the number of rows and $m$ is the number of columns of the matrix.

3. Iteration (Without Extra Space)

Intuition

Since pixel values are at most 255, we can encode both the original value and the new average in a single integer.
We store the new average in the upper bits (by multiplying by 256) and keep the original in the lower bits.
During computation, we extract the original value using modulo 256.
After processing all cells, we extract the new values by dividing by 256.

Algorithm

For each cell, compute the average using img[i][j] % 256 to get original values.
Add the new average to the cell by: img[r][c] += (average) * 256.
After processing all cells, do a second pass to extract the new values.
For each cell, set img[r][c] = img[r][c] / 256.
Return the modified matrix.

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(img), len(img[0])
        LIMIT = 256

        for r in range(ROWS):
            for c in range(COLS):
                total, cnt = 0, 0
                for i in range(max(0, r - 1), min(ROWS, r + 2)):
                    for j in range(max(0, c - 1), min(COLS, c + 2)):
                        total += img[i][j] % LIMIT
                        cnt += 1
                img[r][c] += (total // cnt) * LIMIT

        for r in range(ROWS):
            for c in range(COLS):
                img[r][c] //= LIMIT

        return img

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$ extra space.

Where $n$ is the number of rows and $m$ is the number of columns of the matrix.

4. Bit Mask

Intuition

This approach is similar to the previous one but uses bit manipulation instead of multiplication and division.
We use XOR and bit shifting to store the new average in the upper 8 bits.
The original value occupies the lower 8 bits (since values are 0 to 255).
This is slightly more efficient as bit operations are faster than arithmetic operations.

Algorithm

For each cell, compute the average using img[i][j] % 256 (or & 255) to get original values.
Store the new average in the upper bits using XOR and left shift: img[r][c] ^= (average << 8).
After processing all cells, do a second pass.
For each cell, right shift by 8 bits to extract the new value: img[r][c] >>= 8.
Return the modified matrix.

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(img), len(img[0])

        for r in range(ROWS):
            for c in range(COLS):
                total, cnt = 0, 0
                for i in range(r - 1, r + 2):
                    for j in range(c - 1, c + 2):
                        if i < 0 or i == ROWS or j < 0 or j == COLS:
                            continue
                        total += img[i][j] % 256
                        cnt += 1
                img[r][c] ^= ((total // cnt) << 8)

        for r in range(ROWS):
            for c in range(COLS):
                img[r][c] >>= 8
        return img

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$ extra space.

Where $n$ is the number of rows and $m$ is the number of columns of the matrix.

Common Pitfalls

Off-by-One Errors in Neighbor Iteration

When iterating through the 3x3 window centered at cell (r, c), it is easy to make off-by-one errors with the loop bounds. For example, using range(r - 1, r + 1) only covers two rows instead of three. The correct bounds are range(r - 1, r + 2) to include r - 1, r, and r + 1. Similarly, forgetting to check boundary conditions like 0 <= i < ROWS can cause index out of bounds errors.

Using Modified Values Instead of Original Values

When modifying the matrix in place without extra space, a common mistake is reading already-modified values when computing neighbors. If cell (i, j) has been updated before processing cell (r, c), using img[i][j] directly gives the wrong result. The in-place solutions address this by encoding both original and new values in the same cell using bit manipulation or arithmetic (multiplying/dividing by 256), ensuring original values can always be extracted during computation.