Problem

An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 1 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{array} \xrightarrow{\text{Image Smoother}} \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array} $$

1
2
3
4
5
6

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

Example 2

$$ \Huge \begin{array}{|c|c|c|} \hline 100 & 200 & 100 \\ \hline 200 & 50 & 200 \\ \hline 100 & 200 & 100 \\ \hline \end{array} \xrightarrow{\text{Image Smoother}} \begin{array}{|c|c|c|} \hline 137 & 141 & 137 \\ \hline 141 & 138 & 141 \\ \hline 137 & 141 & 137 \\ \hline \end{array} $$

1
2
3
4
5
6

Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

Constraints

  • m == img.length
  • n == img[i].length
  • 1 <= m, n <= 200
  • 0 <= img[i][j] <= 255

Solution

Method 1 – Brute Force with Bounds Checking

Intuition

For each cell, we want the average of itself and its neighbors. We can check all 3x3 cells around each position, sum their values, count them, and take the floor of the average.

Approach

  1. For each cell (i, j) in the matrix:
    • Initialize sum and count to 0.
    • For each neighbor (di, dj) in [-1, 0, 1]:
      • If (i+di, j+dj) is in bounds, add its value to sum and increment count.
    • Set the result cell to sum // count.
  2. Return the resulting matrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size(), n = img[0].size();
        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int s = 0, c = 0;
                for (int di = -1; di <= 1; ++di) {
                    for (int dj = -1; dj <= 1; ++dj) {
                        int ni = i + di, nj = j + dj;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                            s += img[ni][nj];
                            ++c;
                        }
                    }
                }
                ans[i][j] = s / c;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func imageSmoother(img [][]int) [][]int {
    m, n := len(img), len(img[0])
    ans := make([][]int, m)
    for i := range ans {
        ans[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            s, c := 0, 0
            for di := -1; di <= 1; di++ {
                for dj := -1; dj <= 1; dj++ {
                    ni, nj := i+di, j+dj
                    if ni >= 0 && ni < m && nj >= 0 && nj < n {
                        s += img[ni][nj]
                        c++
                    }
                }
            }
            ans[i][j] = s / c
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int s = 0, c = 0;
                for (int di = -1; di <= 1; ++di) {
                    for (int dj = -1; dj <= 1; ++dj) {
                        int ni = i + di, nj = j + dj;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                            s += img[ni][nj];
                            ++c;
                        }
                    }
                }
                ans[i][j] = s / c;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun imageSmoother(img: Array<IntArray>): Array<IntArray> {
        val m = img.size
        val n = img[0].size
        val ans = Array(m) { IntArray(n) }
        for (i in 0 until m) {
            for (j in 0 until n) {
                var s = 0
                var c = 0
                for (di in -1..1) {
                    for (dj in -1..1) {
                        val ni = i + di
                        val nj = j + dj
                        if (ni in 0 until m && nj in 0 until n) {
                            s += img[ni][nj]
                            c++
                        }
                    }
                }
                ans[i][j] = s / c
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def imageSmoother(self, img: list[list[int]]) -> list[list[int]]:
        m, n = len(img), len(img[0])
        ans = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                s = c = 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:
                            s += img[ni][nj]
                            c += 1
                ans[i][j] = s // c
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn image_smoother(img: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let m = img.len();
        let n = img[0].len();
        let mut ans = vec![vec![0; n]; m];
        for i in 0..m {
            for j in 0..n {
                let mut s = 0;
                let mut c = 0;
                for di in -1..=1 {
                    for dj in -1..=1 {
                        let ni = i as isize + di;
                        let nj = j as isize + dj;
                        if ni >= 0 && ni < m as isize && nj >= 0 && nj < n as isize {
                            s += img[ni as usize][nj as usize];
                            c += 1;
                        }
                    }
                }
                ans[i][j] = s / c;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    imageSmoother(img: number[][]): number[][] {
        const m = img.length, n = img[0].length;
        const ans = Array.from({length: m}, () => Array(n).fill(0));
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                let s = 0, c = 0;
                for (let di = -1; di <= 1; ++di) {
                    for (let dj = -1; dj <= 1; ++dj) {
                        const ni = i + di, nj = j + dj;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                            s += img[ni][nj];
                            c++;
                        }
                    }
                }
                ans[i][j] = Math.floor(s / c);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the dimensions of the image, since we visit each cell and its neighbors.
  • 🧺 Space complexity: O(mn), for the output matrix.