💬 Discord
Sign In
NeetCode #889LC-661EasyMath & Geometry
← Back to All Problems

#889 · #661 · Image Smoother(图片平滑器)

📌 Problem Statement & Constraints

Given an m x n integer matrix img representing an image, return the smoothed image in which each cell becomes the floor of the average of itself and all its up-to-eight neighbours (the neighbourhood is clipped at the borders). Constraints: 1 <= m, n <= 200, 0 <= img[i][j] <= 255.

💡 Core Algorithmic Approaches

  1. For each cell, examine the 3x3 neighbourhood centred on it.
  2. Sum the values of the in-bounds cells and count how many there were.
  3. Set the output cell to the integer (floor) average total // cnt.
  4. Write into a separate result array so that already-smoothed values are never used as inputs.

💻 Benchmark Python3 Implementation

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        m, n = len(img), len(img[0])
        res = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                total = 0
                cnt = 0
                for di in (-1, 0, 1):
                    for dj in (-1, 0, 1):
                        ni, nj = i + di, j + dj
                        if 0 <= ni < m and 0 <= nj < n:
                            total += img[ni][nj]
                            cnt += 1
                res[i][j] = total // cnt      # floor average
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): nine constant-time checks per cell.
💾 Space Complexity
O(m * n): the output image.

⚠️ Interview Pitfalls & Follow-ups

  • Dividing by 9 unconditionally: border and corner cells have fewer neighbours, so the divisor must be the actual in-bounds count.
  • Smoothing in place: cells written earlier would contaminate later ones; a separate output array is required.
  • Rounding instead of flooring: the problem specifies the floor of the average.
  • Using math.floor on a float: integer division total // cnt is exact and simpler.