Image Smoother

• LeetCode: Image Smoother

• Problem:

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. 

If a cell has less than 8 surrounding cells, then use as many as you can.

• Note:

1. The value in the given matrix is in the range of [0, 255].

2. The length and width of the given matrix are in the range of [1, 150].

• Examples:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (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

• Analysis:

arr[i][j] = floor((arr[i - 1][j - 1] + arr[i - 1][j] + arr[i - 1][j + 1] + arr[i][j - 1] + arr[i][j] + arr[i][j + 1]

                  + arr[i + 1][j - 1] + arr[i + 1][j] + arr[i + 1][j + 1]) / 9), 

                  0 <= i - 1 < i < i + 1 < row, 0 <= j - 1 < j < j + 1 < col

• Code - Java:

class Solution {
    public int[][] imageSmoother(int[][] M) {
        int m = M.length;
        if (m == 0) {
            return new int[0][0];
        }
        int n = M[0].length;
        if (n == 0) {
            return new int[m][0];
        }
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = helper(M, i, j, m, n);
            }
        }
        return result;
    }
    private int helper(int[][] M, int i, int j, int m, int n) {
        int sum = M[i][j];
        int count = 1;
        if (i - 1 >= 0) {
            sum += M[i - 1][j];
            count++;
        }
        if (i + 1 < m) {
            sum += M[i + 1][j];
            count++;
        }
        if (j - 1 >= 0) {
            sum += M[i][j - 1];
            count++;
        }
        if (j + 1 < n) {
            sum += M[i][j + 1];
            count++;
        }
        if (i - 1 >= 0 && j - 1 >= 0) {
            sum += M[i - 1][j - 1];
            count++;
        }
        if (i - 1 >= 0 && j + 1 < n) {
            sum += M[i - 1][j + 1];
            count++;
        }
        if (i + 1 < m && j - 1 >= 0) {
            sum += M[i + 1][j - 1];
            count++;
        }
        if (i + 1 < m && j + 1 < n) {
            sum += M[i + 1][j + 1];
            count++;
        }
        return sum / count;
    }
}

• Code - C++:

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        int m = M.size();
        if (m == 0) {
            return vector<vector<int>>();
        }
        int n = M[0].size();
        if (n == 0) {
            return vector<vector<int>>();
        }
        vector<vector<int>> result(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = helper(M, i, j, m, n);
            }
        }
        return result;
    }
    int helper(vector<vector<int>>& M, int i, int j, int m, int n) {
        int sum = M[i][j];
        int count = 1;
        if (i - 1 >= 0) {
            sum += M[i - 1][j];
            count++;
        }
        if (i + 1 < m) {
            sum += M[i + 1][j];
            count++;
        }
        if (j - 1 >= 0) {
            sum += M[i][j - 1];
            count++;
        }
        if (j + 1 < n) {
            sum += M[i][j + 1];
            count++;
        }
        if (i - 1 >= 0 && j - 1 >= 0) {
            sum += M[i - 1][j - 1];
            count++;
        }
        if (i - 1 >= 0 && j + 1 < n) {
            sum += M[i - 1][j + 1];
            count++;
        }
        if (i + 1 < m && j - 1 >= 0) {
            sum += M[i + 1][j - 1];
            count++;
        }
        if (i + 1 < m && j + 1 < n) {
            sum += M[i + 1][j + 1];
            count++;
        }
        return sum / count;
    }
};

• Code - Python:

class Solution(object):
    def imageSmoother(self, M):
        """
        :type M: List[List[int]]
        :rtype: List[List[int]]
        """
        m = len(M)
        if m == 0:
            return []
        n = len(M[0])
        if n == 0:
            return []
        result = [[0 for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                result[i][j] = self.helper(M, i, j, m, n)
        return result

    def helper(self, M, i, j, m, n):
        sumVal, count = M[i][j], 1
        if i - 1 >= 0:
            sumVal += M[i - 1][j]
            count += 1
        if i + 1 < m:
            sumVal += M[i + 1][j]
            count += 1
        if j - 1 >= 0:
            sumVal += M[i][j - 1]
            count += 1
        if j + 1 < n:
            sumVal += M[i][j + 1]
            count += 1
        if i - 1 >= 0 and j - 1 >= 0:
            sumVal += M[i - 1][j - 1]
            count += 1
        if i - 1 >= 0 and j + 1 < n:
            sumVal += M[i - 1][j + 1]
            count += 1
        if i + 1 < m and j - 1 >= 0:
            sumVal += M[i + 1][j - 1]
            count += 1
        if i + 1 < m and j + 1 < n:
            sumVal += M[i + 1][j + 1]
            count += 1
        return sumVal / count

• Time Complexity: O(MN), M is the row count of the input matrix, N is the column count of the input matrix

• Space Complexity: O(MN), M is the row count of the input matrix, N is the column count of the input matrix