algoadvance

Leetcode 661. Image Smoother

Problem Statement

The problem from LeetCode-661, “Image Smoother,” can be described as follows:

Given a 2D integer matrix M representing an image, return a smoothed version of the image. The value of each cell in the smoothed image is the average of all the values in the corresponding 3x3 grid in the original matrix (including the cell itself). If a cell has fewer than 9 neighbors due to the edge of the matrix, the average should be calculated using the existing neighbors.

Constraints:

Clarifying Questions

Before we start coding, here are some clarifying questions and assumptions:

  1. Q: How should the averaging be handled for the borders and corners of the matrix? A: For cells on the borders and corners, consider only the available neighbors.

  2. Q: Is the original matrix M mutable, or should we return a new matrix as the result? A: Return a new matrix as the result.

  3. Q: Should the average be rounded up or down? A: The average should be floored (use integer division).

Strategy

  1. Setup a result matrix: We’ll create a new matrix result of the same dimensions as M.
  2. Iterate through each cell of M:
    • For each cell (i, j), calculate the sum of the values of the 3x3 grid.
    • To get the sum, iterate through the range [i-1, i+1] for rows and [j-1, j+1] for columns.
    • Ensure the indices are within bounds.
  3. Calculate the average:
    • Set the value of result[i][j] as the floor of the above-calculated sum divided by the number of valid cells.
  4. Return the result matrix.

Code

public class ImageSmoother {
    public int[][] imageSmoother(int[][] M) {
        int rows = M.length;
        int cols = M[0].length;
        int[][] result = new int[rows][cols];
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                result[i][j] = calculateAverage(M, i, j, rows, cols);
            }
        }
        
        return result;
    }

    private int calculateAverage(int[][] M, int i, int j, int rows, int cols) {
        int sum = 0;
        int count = 0;
        
        for (int ni = Math.max(0, i - 1); ni <= Math.min(rows - 1, i + 1); ++ni) {
            for (int nj = Math.max(0, j - 1); nj <= Math.min(cols - 1, j + 1); ++nj) {
                sum += M[ni][nj];
                count++;
            }
        }
        
        return sum / count;
    }

    public static void main(String[] args) {
        ImageSmoother smoother = new ImageSmoother();
        int[][] M = {
            {1, 1, 1},
            {1, 0, 1},
            {1, 1, 1}
        };
        int[][] result = smoother.imageSmoother(M);
        
        for (int[] row : result) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

Time Complexity

The time complexity of this solution is O(m*n) where m is the number of rows and n is the number of columns in the matrix M. This is because we iterate through each cell exactly once, and for each cell, we examine a constant number of neighbors (at most 9). The calculateAverage function itself runs in O(1) time due to constant bounds on the neighborhood size.

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