algoadvance

Leetcode 661. Image Smoother

Problem Statement

The problem ‘Image Smoother’ can be found on LeetCode as problem number 661. Given a 2D integer matrix M representing the grayscale of an image, you need to return the smoothed version of the image. The value of each cell in the smoothed version of the image is the average of all the 8 surrounding cells and itself. If a cell has fewer than 8 neighbors, then the average is calculated based on the available neighbors.

Here is the formal description:

Given a 2D integer matrix `M` representing the grayscale of an image, return the smoothed version of the image.

Input:
- An integer matrix `M` representing the grayscale of an image.

Output:
- Return a matrix `result` such that `result[i][j]` is the average of `M[i][j]` and all of its 8 surrounding cells. Rounded down to the nearest integer in case of fractional values.

Clarifying Questions

  1. Can the matrix be empty?
    • Assume that the matrix will always contain at least one element.
  2. How should borders be handled?
    • Borders should be handled by taking the average of the available neighbors only.
  3. What range of values can be in the matrix?
    • Typically, grayscale values are between 0 and 255, but we should account for general integer values.

Strategy

  1. Loop Through Each Cell: We’ll iterate through each cell in the matrix M.
  2. Calculate Neighbor Average: For each cell, we’ll calculate the average of all the available neighbors and itself.
  3. Handle Boundaries: Ensure to check boundaries to avoid accessing invalid indices.
  4. Store Results: Store the results in a new matrix result.
  5. Round Down: Use integer division to round down to the nearest integer.

Code

Here is the C++ code to solve the problem:

#include <vector>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
        if (M.empty()) return {};
        
        int rows = M.size();
        int cols = M[0].size();
        vector<vector<int>> result(rows, vector<int>(cols, 0));
        
        // Directions array representing 8 possible movements and the cell itself
        constexpr int directions[9][2] = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},  {0, 0},  {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int sum = 0, count = 0;
                
                for (auto dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
                    
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                        sum += M[nr][nc];
                        ++count;
                    }
                }
                
                result[r][c] = sum / count; // Using integer division for rounding down
            }
        }
        
        return result;
    }
};

Time Complexity

The time complexity of this solution is O(n * m), where n is the number of rows and m is the number of columns of the matrix M. This is because we iterate through each cell exactly once and perform a constant amount of work for each cell in checking the neighbors.

The space complexity is O(n * m) as well, due to the storage of the resultant matrix.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI