top of page

Image Smoother (LeetCode 661): Clean Neighbor Loops

Nov 3
1 min read


For each cell of a grayscale image, replace it with the floor of the average of itself and its up to eight neighbors.

Idea

Loop over the 3x3 block around each cell, skip coordinates outside the grid, and count how many cells you actually used.

def imageSmoother(img):
    m, n = len(img), len(img[0])
    out = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            total = count = 0
            for r in range(i - 1, i + 2):
                for c in range(j - 1, j + 2):
                    if 0 <= r < m and 0 <= c < n:
                        total += img[r][c]
                        count += 1
            out[i][j] = total // count
    return out

Complexity

O(mn) time (9 checks per cell) and O(mn) for the output grid.

Interview follow-up

Asked for O(1) extra space? Values fit in 8 bits, so store the new value in the upper bits of each cell and shift everything right by 8 at the end.

If you want to rehearse explaining solutions like this under time pressure, the Linkjob AI app is something I help build (disclosure: I work on Linkjob AI).

 
 
 

Recent Posts

See All

Comments


bottom of page