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:
- Loop over each cell in the input image.
- 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. - Use a nested loop to go through each of the surrounding cells, including the cell itself.
- Check if the neighbouring cell is within the image boundaries (its indexes are neither less than 0 nor exceeding the image dimensions).
- If the cell is within bounds, add its value to the sum and increment the count.
- After considering all valid neighbours, calculate the average by dividing the sum by the count.
- Assign the rounded down average to the corresponding cell in the output image matrix.
- 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:
-
The algorithm starts by determining the dimensions of the image matrix, which are stored in variables
m
andn
, representing the number of rows and columns, respectively. -
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. -
A nested
for
loop is used to traverse through each cell of the image matriximg
using row indexi
and column indexj
. -
For each cell (i,j), we initialize
s
andcnt
to zero. Heres
will accumulate the sum of the grayscale values of the current cell and its valid neighbours, whilecnt
will count the number of valid neighbouring cells considered in the smoothing operation (including the cell itself). -
Another nested
for
loop iterates over the cells in the 3x3 block centered at (i, j). The ranges of these loops arei-1
toi+1
andj-1
toj+1
, attempting to cover all nine cells in the block including the center cell. -
For every neighbouring cell, the algorithm checks if its coordinates
(x, y)
are within the image's boundaries using0 <= x < m
and0 <= y < n
. This ensures we do not attempt to access cells outside the array, which would result in an 'index out of range' error. -
Only valid neighbours are included in the average calculation by adding their values to the
s
and incrementing thecnt
. -
Once all valid neighbours are considered, the algorithm computes the average value by dividing
s
bycnt
. Integer division is used (//
in Python), which gives us a rounded down result as required. -
The calculated average is then assigned to the corresponding cell in the
ans
matrix. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example. Imagine we have the following 3x3 grayscale image matrix:
[ [100, 200, 100], [200, 300, 200], [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.
-
We determine the dimensions of the image, which here are
m = 3
andn = 3
. -
We create an output matrix
ans
with the same dimensions, all initialized to zero:
[ [0, 0, 0], [0, 0, 0], [0, 0, 0] ]
-
Using a nested
for
loop, we traverse each cell. We'll focus on the central cell (i=1, j=1). -
Initially, let
s = 0
andcnt = 0
. -
The nested
for
loop runs over the neighbours of the central cell. The loop ranges fromi-1
toi+1
andj-1
toj+1
, meaning it covers all nine cells in the block. -
We check each cell in this range to see if they are within the boundaries.
-
As all cells are within the boundary for the central cell, we add each cell's value to
s
and incrementcnt
for each cell. So we end up with:
s = 100+200+100+200+300+200+100+200+100 = 1500 cnt = 9 (including the central cell itself)
-
We calculate the average grayscale value by integer division of
s
bycnt
, which is1500 // 9 = 166
. -
We place the average value in the central cell of the output:
[ [0, 0, 0], [0, 166, 0], [0, 0, 0] ]
- After repeating steps 3-9 for all other cells and adjusting the boundary cases accordingly, the final smoothed image matrix becomes:
[ [150, 183, 150], [183, 166, 183], [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.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!