661. Image Smoother

Approach 1: Iterating through grid

class Solution(object):
    def imageSmoother(self, M):
        """
        :type M: List[List[int]]
        :rtype: List[List[int]]
        """
        R, C = len(M), len(M[0])
        ans = [[0] * C for _ in M]

        for r in range(R):
            for c in range(C):
                count = 0
                for nr in (r-1, r, r+1):
                    for nc in (c-1, c, c+1):
                        if 0 <= nr < R and 0 <= nc < C:
                            ans[r][c] += M[nr][nc]
                            count += 1
                ans[r][c] /= count
                
        return ans

This solution is clearly the most naive one, by iterating over element and smoothening it

Time Complexity: O(N), where N is the total number of pixels

Space Complexity: O(1)

Approach 2: Using If over Loops

class Solution(object):
    def imageSmoother(self, M):
        """
        :type M: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(M)
        n = len(M[0])
        res = [[i for i in row] for row in M]
        for i in range(m):
            for j in range(n):
                total = M[i][j]
                count = 1
                if i > 0:
                    total += M[i-1][j]
                    count += 1
                if j > 0:
                    total += M[i][j - 1]
                    count += 1
                if i < m - 1:
                    total += M[i+1][j]
                    count += 1
                if j < n - 1:
                    total += M[i][j+1]
                    count += 1
                if i > 0 and j > 0:
                    total += M[i-1][j-1]
                    count += 1
                if i < m - 1 and j < n - 1:
                    total += M[i+1][j+1]
                    count += 1
                if i > 0 and j < n - 1:
                    total += M[i-1][j+1]
                    count += 1
                if i < m - 1 and j > 0:
                    total += M[i+1][j-1]
                    count += 1
                res[i][j] = total / count
        return res

The reason why this approach is better is because the solution does not need to loop over to the element and then check if it is in-bound, it can combine those 2 steps and this results in a faster run-time even though the time complexity remains the same.

This also avoids the overhead of declaring those tuples, and defining loops over them as in lines 13 and 14 in the first solution

Time Complexity: O(N), where N is the total number of pixels

Space Complexity: O(1)