Problem statement

https://leetcode.com/problems/image-smoother/

Solution

There are a lot of different ways to code this problem, here is solution using convolutions: it can potentially work faster for bigger kernels. What we need to do is to evaluate two convolutions: one with matrix M and another with matrix with all ones - in this way we understand how many terms we have, and then divide one by another.

Complexity

It is O(9mn) for time and O(mn) for space.

Code

from scipy.ndimage import convolve
import numpy as np

class Solution:
    def imageSmoother(self, M):
        m, n = len(M), len(M[0])
        T = [[1]*n for _ in range(m)]
        k = [[1,1,1],[1,1,1],[1,1,1]]
        t1 = convolve(M, k, mode = "constant")
        t2 = convolve(T, k, mode = "constant")
        return [[i//j for i, j in zip(r1, r2)] for r1, r2 in zip(t1, t2)]

Remark

Or just do what is asked in O(9mn) time, iterating all pixels. We can also do it in place if instead 8 bits we will create 16 bits numbers and first write data to the last 8 bits and in the second run we remove first 8 bits.