Image Smoother

How it works

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.

Steps

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

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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int ROWS = img.size(), COLS = img[0].size();

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                int total = 0, cnt = 0;
                for (int i = r - 1; i <= r + 1; i++) {
                    for (int j = c - 1; j <= c + 1; j++) {
                        if (i < 0 || i >= ROWS || j < 0 || j >= COLS) {
                            continue;
                        }
                        total += img[i][j] % 256;
                        cnt++;
                    }
                }
                img[r][c] ^= ((total / cnt) << 8);
            }
        }

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                img[r][c] >>= 8;
            }
        }
        return img;
    }
};