Image Smoother - Leetcode Solution

Problem Statement:

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 including itself, then use as many as you can.

Example:

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.83333...) = 0 For the point (1,1): floor(8/9) = floor(0.88888...) = 0

Solution:

We can use a 2D array to go through each cell of the given matrix and then use a nested for loop to access the 8 surrounding cells of that cell. We can then calculate the average of all 9 cells and store it in another matrix of the same size as the original matrix.

To implement this, we will create a new matrix of the same size as the original matrix and initialize all its values to 0. Then, we will traverse the cells of the original matrix one by one and calculate the sum of all the 9 cells including the current cell itself. We will then divide this sum by the number of valid cells (either 8 or less if cells are on the border) and round down to the nearest integer. This value will be stored in the corresponding cell of the new matrix.

Algorithm:

1. Create a new matrix of the same size as the original matrix.
2. Initialize all cells of the new matrix to 0.
3. Traverse each cell of the original matrix.
4. For each cell, calculate the sum of all 9 cells (including itself) and count the number of valid cells (before or after the border).
5. Calculate the average by dividing the sum by the number of valid cells and round down to the nearest integer.
6. Store this value in the corresponding cell of the new matrix.
7. Return the new matrix.

Code:

class Solution { public: vector<vector<int>> imageSmoother(vector<vector<int>>& M) { vector<vector<int>> res(M.size(), vector<int>(M[0].size())); for (int i = 0; i < M.size(); ++i) { for (int j = 0; j < M[0].size(); ++j) { int sum = 0, count = 0; for (int dr = -1; dr <= 1; ++dr) { for (int dc = -1; dc <= 1; ++dc) { int nr = i + dr, nc = j + dc; if (0 <= nr && nr < M.size() && 0 <= nc && nc < M[0].size()) { ++count; sum += M[nr][nc]; } } } res[i][j] = sum / count; } } return res; } };

Complexity Analysis:

Time Complexity: O(mn) - where m and n are the number of rows and columns in the input matrix. Space Complexity: O(mn) - we are creating an output matrix of the same size as the input matrix.

1