LeetCode 661: Image Smoother (3×3 Neighborhood Average with Boundary Check)
LeetCode 661MatrixSimulationToday we solve LeetCode 661 - Image Smoother.
Source: https://leetcode.com/problems/image-smoother/
English
Problem Summary
Given an m x n grayscale image matrix img, each cell in the output should be the floor of the average value of the valid cells in its surrounding 3×3 block (including itself).
Key Insight
For every pixel (r, c), the candidate neighbors are fixed: all offsets in {-1,0,1} × {-1,0,1}.
We only count positions that stay inside bounds, accumulate sum and count, then write sum / count.
Algorithm
1) Let rows = img.length, cols = img[0].length, and allocate ans.
2) For each cell (r, c), iterate dr and dc from -1 to 1.
3) If neighbor (nr, nc) = (r+dr, c+dc) is valid, add img[nr][nc] to sum and increment count.
4) Set ans[r][c] = sum / count (integer floor division).
5) Return ans.
Complexity Analysis
Time: O(mn) (each cell checks at most 9 neighbors).
Space: O(mn) for output matrix.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[][] imageSmoother(int[][] img) {
int rows = img.length;
int cols = img[0].length;
int[][] ans = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int sum = 0;
int count = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr;
int nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
count++;
}
}
}
ans[r][c] = sum / count;
}
}
return ans;
}
}func imageSmoother(img [][]int) [][]int {
rows := len(img)
cols := len(img[0])
ans := make([][]int, rows)
for i := 0; i < rows; i++ {
ans[i] = make([]int, cols)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
sum, count := 0, 0
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
sum += img[nr][nc]
count++
}
}
}
ans[r][c] = sum / count
}
}
return ans
}class Solution {
public:
vector> imageSmoother(vector>& img) {
int rows = (int)img.size();
int cols = (int)img[0].size();
vector> ans(rows, vector(cols, 0));
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
int sum = 0, count = 0;
for (int dr = -1; dr <= 1; ++dr) {
for (int dc = -1; dc <= 1; ++dc) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
++count;
}
}
}
ans[r][c] = sum / count;
}
}
return ans;
}
}; class Solution:
def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
rows, cols = len(img), len(img[0])
ans = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
total = 0
count = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
total += img[nr][nc]
count += 1
ans[r][c] = total // count
return ansvar imageSmoother = function(img) {
const rows = img.length;
const cols = img[0].length;
const ans = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
let sum = 0;
let count = 0;
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
count++;
}
}
}
ans[r][c] = Math.floor(sum / count);
}
}
return ans;
};中文
题目概述
给定一个灰度图矩阵 img，输出矩阵中每个位置的值是该位置周围 3×3 邻域（包含自身）中所有有效坐标像素值的平均值向下取整。
核心思路
对每个像素 (r, c)，固定遍历九个偏移量组合：dr, dc ∈ {-1,0,1}。
只有越界检查通过的邻居才参与统计，最终写入 sum / count。
算法步骤
1）获取行列数并创建答案矩阵 ans。
2）双层循环遍历每个位置 (r, c)。
3）再用两层 dr/dc 枚举 3×3 邻域，累加有效邻居的值与数量。
4）令 ans[r][c] = sum / count（整除即向下取整）。
5）返回 ans。
复杂度分析
时间复杂度：O(mn)（每个格子最多看 9 个邻居）。
空间复杂度：O(mn)（输出矩阵）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[][] imageSmoother(int[][] img) {
int rows = img.length;
int cols = img[0].length;
int[][] ans = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int sum = 0;
int count = 0;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int nr = r + dr;
int nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
count++;
}
}
}
ans[r][c] = sum / count;
}
}
return ans;
}
}func imageSmoother(img [][]int) [][]int {
rows := len(img)
cols := len(img[0])
ans := make([][]int, rows)
for i := 0; i < rows; i++ {
ans[i] = make([]int, cols)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
sum, count := 0, 0
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
sum += img[nr][nc]
count++
}
}
}
ans[r][c] = sum / count
}
}
return ans
}class Solution {
public:
vector> imageSmoother(vector>& img) {
int rows = (int)img.size();
int cols = (int)img[0].size();
vector> ans(rows, vector(cols, 0));
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
int sum = 0, count = 0;
for (int dr = -1; dr <= 1; ++dr) {
for (int dc = -1; dc <= 1; ++dc) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
++count;
}
}
}
ans[r][c] = sum / count;
}
}
return ans;
}
}; class Solution:
def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
rows, cols = len(img), len(img[0])
ans = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
total = 0
count = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
total += img[nr][nc]
count += 1
ans[r][c] = total // count
return ansvar imageSmoother = function(img) {
const rows = img.length;
const cols = img[0].length;
const ans = Array.from({ length: rows }, () => Array(cols).fill(0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
let sum = 0;
let count = 0;
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
sum += img[nr][nc];
count++;
}
}
}
ans[r][c] = Math.floor(sum / count);
}
}
return ans;
};
Comments