Leetcode 661. Image Smoother

Problem Explanation

In this problem, we're given a 2D matrix, which represents the grayscale of an image. Each cell in the matrix has a range of [0,255] representing a gray scale pixel of an image. We are asked to write a smoother to average of values of neighbouring cells and itself. The smaller the number, the darker the cell.

A cell in the matrix can at most have 8 neighbours (top, bottom, left, right and the 4 diagonals). If a cell has less than 8 neighbours, we take as many as we can. After calculating the average, we round down the average (pick the largest integer that is less than or equal to the calculated average).

For instance, let's take the following matrix:

1[[1,1,1],
2 [1,0,1],
3 [1,1,1]]

The value of the cell at position (1,1) is 0. All of its neighbors and itself sum up to 8 . Hence, the average is 8/9 or 0.88888889. After rounding down, we get 0. That's why all the values in the output is 0

Approach and Algorithm

This problem can be solved through nested loops. We will loop through each cell of the Matrix and find out its neighbours (top, bottom, left, right and the 4 diagonals) if they exist. After that, we calculate the sum of the values of the neighbor cells and count the number of neighbor cells. Dividing the sum by the count and taking the floor of the result will give us the new value of the cell in the image.

Python Solution

1
2python
3class Solution:
4    def imageSmoother(self, M: List[List[int]]) -> List[List[int]]:
5        m, n = len(M), len(M[0])
6        res = []
7        
8        for i in range(m):
9            row = []
10            for j in range(n):
11                sm = cnt = 0
12                for dx in [-1, 0, 1]:
13                    for dy in [-1, 0, 1]:
14                        ni, nj = i + dx, j + dy
15                        if 0 <= ni < m and 0 <= nj < n:
16                            sm += M[ni][nj]
17                            cnt += 1
18                row.append(sm // cnt)
19            res.append(row)
20            
21        return res

Java Solution

1
2java
3class Solution {
4    public int[][] imageSmoother(int[][] M) {
5        int[][] res = new int[M.length][M[0].length];
6        for(int i=0; i<M.length; i++){
7            for(int j=0; j<M[0].length; j++){
8                res[i][j] = getAvg(M, i, j);
9            }
10        }
11        return res;
12    }
13    
14    private int getAvg(int[][] M, int i, int j){
15        int sum = 0;
16        int count = 0;
17        for(int x=i-1;x<=i+1;x++){
18            for(int y=j-1;y<=j+1;y++){
19                if(x>=0 && y>=0 && x<M.length && y<M[0].length){
20                    sum += M[x][y];
21                    count++;
22                }
23            }
24        }
25        return sum / count;
26    }
27}

Javascript Solution

1
2javascript
3var imageSmoother = function(M) {
4    let res = [];
5    for(let i=0; i<M.length; i++) {
6        res[i] = [];
7        for(let j=0; j<M[0].length; j++) {
8            let sum = 0, count = 0;
9            for(let x=i-1; x<=i+1; x++) {
10                for(let y=j-1; y<=j+1; y++) {
11                    if(x>=0 && y>=0 && x<M.length && y<M[0].length) {
12                        sum += M[x][y];
13                        count++;
14                    }
15                }
16            }
17            res[i][j] = Math.floor(sum / count);
18        }
19    }
20    return res;
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
6        int dx[9] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
7        int dy[9] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
8        int n = M.size(), m = M[0].size();
9        vector<vector<int>> res(n, vector<int>(m, 0));
10
11        for(int i = 0; i < n; i++) {
12            for(int j = 0; j < m; j++) {
13                int sum = 0, count = 0;
14                for(int k = 0; k < 9; k++) {
15                    int x = i + dx[k], y = j + dy[k];
16 
17                    if(x >= 0 && x < n && y >= 0 && y < m) {
18                        sum += M[x][y];
19                        count++;
20                    }
21                }
22                res[i][j] = sum / count;
23            }
24        }
25        return res;
26    }
27};

C# Solution

1
2csharp
3public class Solution {
4    public int[][] ImageSmoother(int[][] M) {
5        int rows = M.Length;
6        int cols = M[0].Length;
7        
8        int[][] result = new int[rows][];
9        
10        for (int i = 0; i < rows; i++) {
11            result[i] = new int[cols];
12            for (int j = 0; j < cols; j++) {
13                int sum = 0, count = 0;
14                
15                for (int x = i - 1; x <= i + 1; x++) {
16                    for (int y = j - 1; y <= j + 1; y++) {
17                        if (x >= 0 && x < rows && y >= 0 && y < cols) {
18                            sum += M[x][y];
19                            count++;
20                        }
21                    }
22                }
23                result[i][j] = sum / count;
24            }
25        }
26        return result;
27    }
28}

In all these solutions, we are creating new matrices for storing the smoothed image, so that we don't overwrite the original matrix while processing.The time complexity for these solutions are O(n^2), where n is the number of cells in the matrix. This is because for each cell in the matrix, we perform a fixed number of operations to sum up its neighbours and itself, divide, and finally substitute the new value.

The space complexity is also O(n^2), where n is the number of cells in the matrix. This is because we create a new matrix of equal size to store the final result.

In conclusion, by dividing complicated tasks into small steps and leveraging the inner loop for computation, we can effectively solve the problem. However, the performance can be improved if we could find a way to perform the calculation without creating a new matrix, which could potentially reduce the space complexity to O(1). Possible methods could include using a more space-efficient data structure or altering the original matrix in place while still correctly calculating the averages.