661. Image Smoother - Explanation

1. Iteration (Using Extra 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)

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)

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

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.