Image Smoother — Solution in Python, Java & C++
Image Smoother solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.
Image Smoother is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An image smoother replaces each cell of a grayscale image by the average of itself and its eight surrounding cells, rounded down. Cells that fall outside the image are simply not counted, so a corner averages four cells and an edge six.
Given an m × n integer matrix img representing the image, return the smoothed image.
Example 1
Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation: Each corner averages 3/4 = 0 after rounding down.
Example 2
Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Example 3
Input: img = [[5]]
Output: [[5]]
Constraints
1 <= img.length, img[i].length <= 80 <= img[i][j] <= 255
Hints for Image Smoother
Hint 1
For each cell, loop over the nine offsets from (-1,-1) to (1,1).
Hint 2
Skip offsets that leave the grid, and count only the cells you actually used.
Hint 3
Write into a new matrix — smoothing in place would feed already-smoothed values into later averages.
How to solve Image Smoother
For each cell, average the in-bounds cells of its 3 × 3 neighbourhood, writing into a fresh matrix so later cells still read original values.
Approach
- For each
(r, c), loop over the nine offsets(-1..1, -1..1). - Skip offsets outside the grid; sum the rest and count them.
- Write
total // countto the output.
Why it works
Counting only the cells actually visited makes corners average four and edges six, exactly as specified, and the floor division rounds down.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Smoothing in place feeds already-smoothed values into later averages.
Reference solution
Python
def imageSmoother(img):
m, n = len(img), len(img[0])
out = []
for r in range(m):
row = []
for c in range(n):
total = count = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
total += img[nr][nc]
count += 1
row.append(total // count)
out.append(row)
return outJava
public static int[][] imageSmoother(int[][] img) {
int m = img.length, n = img[0].length;
int[][] out = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; 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 < m && nc >= 0 && nc < n) {
sum += img[nr][nc];
count++;
}
}
}
out[r][c] = sum / count;
}
}
return out;
}C++
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int m = (int) img.size(), n = (int) img[0].size();
vector<vector<int>> out(m, vector<int>(n, 0));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; 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 < m && nc >= 0 && nc < n) {
sum += img[nr][nc];
count++;
}
}
}
out[r][c] = sum / count;
}
}
return out;
}JavaScript
var imageSmoother = function(img) {
const m = img.length, n = img[0].length;
const out = [];
for (let r = 0; r < m; r++) {
const row = [];
for (let c = 0; c < n; c++) {
let sum = 0, count = 0;
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
sum += img[nr][nc];
count++;
}
}
}
row.push(Math.floor(sum / count));
}
out.push(row);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal