661. Image Smoother


Problem Description

The task is to write an algorithm for an "image smoother," which is a filter operation applied to each cell of a grayscale image. The image is represented as a 2D integer matrix, where each cell contains a grayscale value. The smoother considers the value of a cell and the values of the eight surrounding cells to calculate an average. This average is then rounded down and placed into the corresponding cell in the resulting image. When cells on the edges or corners of the image do not have eight surrounding cells, the smoother only averages over the existing neighbouring cells. The challenge is to apply this filter correctly, ensuring that boundary conditions are handled and only valid neighbours are included in the average calculation.

Intuition

The solution approach involves a nested loop to traverse each cell in the image. For each cell, a sub-loop considers the surrounding cells within a distance of 1 cell in all directions. To manage cells at the edges and corners that have fewer neighbours, the algorithm checks if each potential neighbouring cell is within the image boundaries before including it in the average calculation.

The steps are:

  1. Loop over each cell in the input image.
  2. Initialize sum (s) and count (cnt) variables for each cell. The sum will hold the total grayscale value sum of the neighbours, and count will keep track of the number of valid neighbours considered.
  3. Use a nested loop to go through each of the surrounding cells, including the cell itself.
  4. Check if the neighbouring cell is within the image boundaries (its indexes are neither less than 0 nor exceeding the image dimensions).
  5. If the cell is within bounds, add its value to the sum and increment the count.
  6. After considering all valid neighbours, calculate the average by dividing the sum by the count.
  7. Assign the rounded down average to the corresponding cell in the output image matrix.
  8. Return the resulting image matrix after the smoother has been applied to all cells.

The solution effectively handles the averaging with the correct denominator for each cell, taking image boundary conditions into account.

Solution Approach

The implementation of the image smoother involves tackling the problem with a brute-force approach, where each cell's value is updated based on its neighbours.

Here's a detailed breakdown of the solution approach:

  1. The algorithm starts by determining the dimensions of the image matrix, which are stored in variables m and n, representing the number of rows and columns, respectively.

  2. An output matrix ans of the same dimensions as the input (img) is created to store the smoothed values. This is initialized to zero for all cells.

  3. A nested for loop is used to traverse through each cell of the image matrix img using row index i and column index j.

  4. For each cell (i,j), we initialize s and cnt to zero. Here s will accumulate the sum of the grayscale values of the current cell and its valid neighbours, while cnt will count the number of valid neighbouring cells considered in the smoothing operation (including the cell itself).

  5. Another nested for loop iterates over the cells in the 3x3 block centered at (i, j). The ranges of these loops are i-1 to i+1 and j-1 to j+1, attempting to cover all nine cells in the block including the center cell.

  6. For every neighbouring cell, the algorithm checks if its coordinates (x, y) are within the image's boundaries using 0 <= x < m and 0 <= y < n. This ensures we do not attempt to access cells outside the array, which would result in an 'index out of range' error.

  7. Only valid neighbours are included in the average calculation by adding their values to the s and incrementing the cnt.

  8. Once all valid neighbours are considered, the algorithm computes the average value by dividing s by cnt. Integer division is used (// in Python), which gives us a rounded down result as required.

  9. The calculated average is then assigned to the corresponding cell in the ans matrix.

  10. After the completion of both nested loops, the matrix ans is fully populated with the smoothed values and is returned as the final result.

The simplicity of the brute-force approach makes it an uncomplicated solution that is easy to understand and implement. However, it does have a time complexity of O(m x n x k), where k is the number of neighbouring cells to consider (in this case, 9), because we are visiting each cell surrounding every cell in the matrix. Using brute force is acceptable here because the size of the smoothing filter is fixed and small.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's illustrate the solution approach using a small example. Imagine we have the following 3x3 grayscale image matrix:

1[ [100, 200, 100],
2  [200, 300, 200],
3  [100, 200, 100] ]

This matrix represents the grayscale values for a 3x3 image. Now, let's walk through the steps to apply the image smoother for the central cell (1,1) with the value 300.

  1. We determine the dimensions of the image, which here are m = 3 and n = 3.

  2. We create an output matrix ans with the same dimensions, all initialized to zero:

1[ [0, 0, 0],
2  [0, 0, 0],
3  [0, 0, 0] ]
  1. Using a nested for loop, we traverse each cell. We'll focus on the central cell (i=1, j=1).

  2. Initially, let s = 0 and cnt = 0.

  3. The nested for loop runs over the neighbours of the central cell. The loop ranges from i-1 to i+1 and j-1 to j+1, meaning it covers all nine cells in the block.

  4. We check each cell in this range to see if they are within the boundaries.

  5. As all cells are within the boundary for the central cell, we add each cell's value to s and increment cnt for each cell. So we end up with:

1   s = 100+200+100+200+300+200+100+200+100 = 1500
2   cnt = 9 (including the central cell itself)
  1. We calculate the average grayscale value by integer division of s by cnt, which is 1500 // 9 = 166.

  2. We place the average value in the central cell of the output:

1[ [0,  0, 0],
2  [0, 166, 0],
3  [0,  0, 0] ]
  1. After repeating steps 3-9 for all other cells and adjusting the boundary cases accordingly, the final smoothed image matrix becomes:
1[ [150, 183, 150],
2  [183, 166, 183],
3  [150, 183, 150] ]

Here's how the boundary cases are averaged for top-left corner cell (i=0, j=0):

  • s = 100+200+200+300, as only 4 cells (including itself) are valid neighbors.
  • cnt = 4.
  • The average is then 600 // 4 = 150.
  • The value 150 is placed in the top-left cell of the output matrix.

The same approach is repeated for other edge cells, considering the valid neighbors. Once all cells are processed, ans matrix is returned as the result of the smoothed image.

Solution Implementation

1class Solution:
2    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
3        # Get the number of rows and columns in the image
4        num_rows, num_cols = len(img), len(img[0])
5      
6        # Initialize an output image with the same dimensions, filled with zeros
7        smoothed_image = [[0] * num_cols for _ in range(num_rows)]
8      
9        # Iterate through each pixel in the image
10        for row in range(num_rows):
11            for col in range(num_cols):
12                # Initialize the sum and count of neighboring pixels
13                pixel_sum = pixel_count = 0
14              
15                # Check all 9 positions in the neighborhood (including the pixel itself)
16                for neighbor_row in range(row - 1, row + 2):
17                    for neighbor_col in range(col - 1, col + 2):
18                        # Ensure the neighbor is within image boundaries before including it
19                        if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:
20                            pixel_count += 1
21                            pixel_sum += img[neighbor_row][neighbor_col]
22              
23                # Calculate the smoothed value for the current pixel
24                # by taking the average of the sum of the neighborhood pixels
25                smoothed_image[row][col] = pixel_sum // pixel_count
26      
27        # Return the smoothed image
28        return smoothed_image
29
1class Solution {
2    public int[][] imageSmoother(int[][] img) {
3        // Get the dimensions of the image
4        int rows = img.length;
5        int cols = img[0].length;
6      
7        // Initialize the smoothed image array
8        int[][] smoothedImg = new int[rows][cols];
9
10        // Iterate through each pixel in the image
11        for (int i = 0; i < rows; ++i) {
12            for (int j = 0; j < cols; ++j) {
13                int sum = 0; // Sum of pixel values in the smoothing window
14                int count = 0; // Number of pixels in the smoothing window
15              
16                // Iterate through the neighboring pixels including the current pixel
17                for (int x = i - 1; x <= i + 1; ++x) {
18                    for (int y = j - 1; y <= j + 1; ++y) {
19                        // Check if the neighbor is within the image boundaries
20                        if (x >= 0 && x < rows && y >= 0 && y < cols) {
21                            count++; // Increment the pixel count
22                            sum += img[x][y]; // Add the pixel value to the sum
23                        }
24                    }
25                }
26
27                // Compute the average pixel value and assign it to the smoothed image
28                smoothedImg[i][j] = sum / count;
29            }
30        }
31
32        // Return the smoothed image
33        return smoothedImg;
34    }
35}
36
1class Solution {
2public:
3    vector<vector<int>> imageSmoother(vector<vector<int>>& image) {
4        int rows = image.size();        // Number of rows in the image
5        int cols = image[0].size();     // Number of columns in the image
6        // Create a 2D vector with the same dimensions as the input image to store the result
7        vector<vector<int>> smoothedImage(rows, vector<int>(cols));
8
9        // Iterate through each cell in the image
10        for (int i = 0; i < rows; ++i) {
11            for (int j = 0; j < cols; ++j) {
12                int sum = 0;   // Sum of the surrounding cell values including itself
13                int count = 0; // Counter for the number of cells included in the sum
14
15                // Iterate through the neighboring cells centered at (i, j)
16                for (int x = i - 1; x <= i + 1; ++x) {
17                    for (int y = j - 1; y <= j + 1; ++y) {
18                        // Check if the neighboring cell (x, y) is within the bounds of the image
19                        if (x >= 0 && x < rows && y >= 0 && y < cols) {
20                            count++;             // Increment the counter for each valid cell
21                            sum += image[x][y];  // Add the cell value to the sum
22                        }
23                    }
24                }
25                // Compute the average value of the surrounding cells and assign to the corresponding cell in the result
26                smoothedImage[i][j] = sum / count;
27            }
28        }
29        // Return the resulting smooth image
30        return smoothedImage;
31    }
32};
33
1function imageSmoother(img: number[][]): number[][] {
2    // Get the dimensions of the image
3    const rows = img.length;
4    const cols = img[0].length;
5  
6    // Define the relative positions of the neighbors around a pixel
7    const neighborOffsets = [
8        [-1, -1], [-1, 0], [-1, 1],
9        [0, -1],  [0, 0],  [0, 1],
10        [1, -1],  [1, 0],  [1, 1]
11    ];
12
13    // Initialize the result image with the same dimensions
14    const resultImage = new Array(rows).fill(0).map(() => new Array(cols).fill(0));
15  
16    for (let row = 0; row < rows; row++) {
17        for (let col = 0; col < cols; col++) {
18            let sum = 0; // Sum of the pixel values in the smooth box
19            let count = 0; // Number of pixels in the smooth box
20
21            // Iterate through all neighbors including the current pixel
22            for (const [offsetRow, offsetCol] of neighborOffsets) {
23                const neighborRow = row + offsetRow;
24                const neighborCol = col + offsetCol;
25              
26                // Check if the neighbor is within the image boundaries
27                if (neighborRow >= 0 && neighborRow < rows && neighborCol >= 0 && neighborCol < cols) {
28                    sum += img[neighborRow][neighborCol]; // Add the neighbor's value to the sum
29                    count++; // Increase the pixel count
30                }
31            }
32
33            // Calculate the smoothed value and assign it to the result image
34            resultImage[row][col] = Math.floor(sum / count);
35        }
36    }
37  
38    // Return the smoothed image
39    return resultImage;
40}
41

Time and Space Complexity

Time Complexity

The given code iterates through every cell of the img matrix, represented by dimensions m x n, where m is the number of rows and n is the number of columns. For each cell (i, j), it considers up to 9 neighboring cells (including the cell itself) in a 3x3 grid. This nested iteration contributes a constant factor of 9 for each cell, because the innermost two loops (over x and y) run at most 3 times each.

Thus, the total time complexity is O(m * n * 9), which simplifies to O(m * n) since 9 is a constant factor and does not affect the asymptotic complexity.

Space Complexity

The space complexity comes from the additional matrix ans that is created to store the smoothed values. It's the same size as the input matrix img, so the space complexity is O(m * n).

No additional space is used that grows with the size of the input, as the variables s (sum of the neighbor values) and cnt (the count of neighbors considered) use constant space. Therefore, the total space complexity remains O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄