# Image Smoother
**Difficulty:** EASY
[External](https://leetcode.com/problems/image-smoother)
Canonical: https://scaleengineer.com/dsa/problems/image-smoother
**Data structures:** Array, Matrix
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Verkada](https://scaleengineer.com/companies/verkada), [Toptal](https://scaleengineer.com/companies/toptal)
---
## Problem
An **image smoother** is a filter of the size `3 x 3` that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

![](https://assets.glich.co/dsa/image-smoother/image0.jpg) 

Given an `m x n` integer matrix `img` representing the grayscale of an image, return _the image after applying the smoother on each cell of it_.

**Example 1:**

![](https://assets.glich.co/dsa/image-smoother/image1.jpg) 

**Input:** img = [[1,1,1],[1,0,1],[1,1,1]]
**Output:** [[0,0,0],[0,0,0],[0,0,0]]
**Explanation:**
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

**Example 2:**

![](https://assets.glich.co/dsa/image-smoother/image2.jpg) 

**Input:** img = [[100,200,100],[200,50,200],[100,200,100]]
**Output:** [[137,141,137],[141,138,141],[137,141,137]]
**Explanation:**
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

**Constraints:**

* `m == img.length`
* `n == img[i].length`
* `1 <= m, n <= 200`
* `0 <= img[i][j] <= 255`

# Approaches
## Brute Force with Extra Space
This approach directly simulates the process described in the problem. We create a new matrix to store the smoothed image. For each cell in the original image, we calculate the average of its 3x3 neighborhood and store the result in the corresponding cell of the new matrix. Using a separate matrix is crucial to ensure that all calculations are based on the original, unmodified pixel values.
**Time:** O(m * n). We iterate through each of the `m * n` cells. For each cell, we perform a constant number of operations (iterating through a 3x3 grid, which is 9 checks and additions). Thus, the complexity is proportional to the number of cells in the image. · **Space:** O(m * n). We allocate a new matrix `smoothedImg` with the same dimensions as the input image to store the results.
**Pros:** Simple and straightforward to implement.; The logic directly follows the problem description, making it easy to reason about correctness.
**Cons:** Requires extra space proportional to the size of the input image, which can be significant for large images.
### Explanation
We initialize a new result matrix, `smoothedImg`, with the same dimensions as the input `img`. We then iterate through every cell `(r, c)` of the `img` matrix. For each cell, we define a 3x3 window around it. We iterate through all 9 positions in this window, from `(r-1, c-1)` to `(r+1, c+1)`. For each position `(nr, nc)` in the window, we check if it's within the valid bounds of the image (i.e., `0 <= nr < m` and `0 <= nc < n`). If the position is valid, we add its pixel value `img[nr][nc]` to a running `totalSum` and increment a `count` of valid neighbors. After checking all 9 positions, we compute the average by dividing `totalSum` by `count` and take the floor value. This computed value is placed in `smoothedImg[r][c]`. After iterating through all cells, the `smoothedImg` matrix contains the final smoothed image and is returned.

```java
class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length;
        int n = img[0].length;
        int[][] smoothedImg = new int[m][n];

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int totalSum = 0;
                int count = 0;

                // Iterate over the 3x3 neighborhood
                for (int i = r - 1; i <= r + 1; i++) {
                    for (int j = c - 1; j <= c + 1; j++) {
                        // Check if the neighbor is within the image bounds
                        if (i >= 0 && i < m && j >= 0 && j < n) {
                            totalSum += img[i][j];
                            count++;
                        }
                    }
                }
                smoothedImg[r][c] = totalSum / count;
            }
        }
        return smoothedImg;
    }
}
```
### Algorithm
- Get the dimensions of the input image, `m` (rows) and `n` (columns).
- Create a new integer matrix `smoothedImg` of size `m x n`.
- Iterate through each cell of the input `img` from row `r = 0` to `m-1`.
- Inside this loop, iterate from column `c = 0` to `n-1`.
- For each cell `(r, c)`, initialize `totalSum = 0` and `count = 0`.
- Iterate through the neighboring rows `i` from `r-1` to `r+1`.
- Inside this loop, iterate through the neighboring columns `j` from `c-1` to `c+1`.
- Check if the neighbor coordinates `(i, j)` are valid (within the matrix bounds).
- If valid, add `img[i][j]` to `totalSum` and increment `count`.
- After the neighborhood loops, calculate the smoothed value `totalSum / count` (integer division handles the floor).
- Assign this value to `smoothedImg[r][c]`.
- After iterating through all cells, return `smoothedImg`.

## In-Place Modification using Bit Manipulation
This approach optimizes the space complexity by modifying the input matrix in-place. Since the original pixel values (0-255) are needed for subsequent calculations, we can't simply overwrite them. Instead, we use bit manipulation to store both the original and the new smoothed value in a single integer cell. The original value is stored in the lower 8 bits, and the new value is stored in the next 8 bits.
**Time:** O(m * n). We traverse the matrix twice. The first pass involves constant work (9 neighborhood checks) for each cell, and the second pass involves a single operation per cell. The total time is `O(m * n) + O(m * n) = O(m * n)`. · **Space:** O(1). The modifications are done in-place on the input matrix. No auxiliary data structures proportional to the input size are used.
**Pros:** Extremely space-efficient, using constant extra space.; Maintains the optimal time complexity.
**Cons:** The logic is more complex due to bit manipulation.; It modifies the input matrix directly, which might not be desirable in all contexts.
### Explanation
The core idea is to use the 32 bits of an integer to store two 8-bit values. The original pixel value (0-255) fits in 8 bits. The new smoothed value also fits in 8 bits. We can store the new value in bits 8-15 and keep the original value in bits 0-7.
The algorithm proceeds in two passes:

**First Pass (Calculation and Encoding):**
- Iterate through every cell `(r, c)` of the `img` matrix.
- For each cell, calculate the smoothed value just like in the brute-force approach. However, when accessing a neighbor's value `img[nr][nc]`, we must retrieve its *original* value. Since previous cells in the iteration might have already been updated, we extract the original value using the bitwise AND operator: `img[nr][nc] & 0xFF`.
- Once the `smoothedValue` is calculated, we encode it into the current cell `img[r][c]`. We shift the `smoothedValue` left by 8 bits (`smoothedValue << 8`) and combine it with the original value using bitwise OR: `img[r][c] = img[r][c] | (smoothedValue << 8)`.

**Second Pass (Decoding):**
- After the first pass, every cell `img[r][c]` contains the new value in its higher bits.
- Iterate through the matrix again.
- For each cell, update its value to the smoothed value by shifting it right by 8 bits: `img[r][c] = img[r][c] >> 8`.

This modifies the matrix in-place and returns it.

```java
class Solution {
    public int[][] imageSmoother(int[][] img) {
        int m = img.length;
        int n = img[0].length;

        // First pass: calculate and store new value in higher bits
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int totalSum = 0;
                int count = 0;

                for (int i = r - 1; i <= r + 1; i++) {
                    for (int j = c - 1; j <= c + 1; j++) {
                        if (i >= 0 && i < m && j >= 0 && j < n) {
                            // Extract original value from lower 8 bits
                            totalSum += img[i][j] & 0xFF;
                            count++;
                        }
                    }
                }
                int smoothedValue = totalSum / count;
                // Store new value in bits 8-15, original value is already in bits 0-7
                img[r][c] |= (smoothedValue << 8);
            }
        }

        // Second pass: update the matrix with the new values
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Extract the new value from higher bits
                img[r][c] = img[r][c] >> 8;
            }
        }

        return img;
    }
}
```
### Algorithm
- Get the dimensions of the input image, `m` and `n`.
- **Pass 1: Calculate and Encode**
  - Iterate through each cell `(r, c)` of the `img` matrix.
  - For each cell, initialize `totalSum = 0` and `count = 0`.
  - Iterate through its 3x3 neighborhood `(i, j)`.
  - If `(i, j)` is a valid coordinate:
    - Extract the original value of the neighbor using `img[i][j] & 0xFF`.
    - Add this original value to `totalSum` and increment `count`.
  - Calculate the `smoothedValue = totalSum / count`.
  - Store the `smoothedValue` in the higher 8 bits of `img[r][c]` by performing a bitwise OR with the value shifted left by 8: `img[r][c] |= (smoothedValue << 8)`.
- **Pass 2: Decode**
  - Iterate through each cell `(r, c)` of the `img` matrix again.
  - Update the cell's value to be the smoothed value by right-shifting by 8 bits: `img[r][c] >>= 8`.
- Return the modified `img` matrix.

# Solutions
### Java

```java
class Solution { public int [][] imageSmoother ( int [][] img ) { int m = img . length ; int n = img [ 0 ]. length ; int [][] ans = new int [ m ][ n ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int s = 0 ; int cnt = 0 ; for ( int x = i - 1 ; x <= i + 1 ; ++ x ) { for ( int y = j - 1 ; y <= j + 1 ; ++ y ) { if ( x >= 0 && x < m && y >= 0 && y < n ) { ++ cnt ; s += img [ x ][ y ]; } } } ans [ i ][ j ] = s / cnt ; } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> imageSmoother(vector<vector<int>> &img) {
    int m = img.size(), n = img[0].size();
    vector<vector<int>> ans(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int s = 0, cnt = 0;
        for (int x = i - 1; x <= i + 1; ++x) {
          for (int y = j - 1; y <= j + 1; ++y) {
            if (x < 0 || x >= m || y < 0 || y >= n)
              continue;
            ++cnt;
            s += img[x][y];
          }
        }
        ans[i][j] = s / cnt;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]: m, n = len(img), len(img[0]) ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): s = cnt = 0 for x in range(i - 1, i + 2): for y in range(j - 1, j + 2): if 0 <= x < m and 0 <= y < n: cnt += 1 s += img[x][y] ans[i][j] = s // cnt return ans

```