# LeetCode 661: Image Smoother ## Problem Restatement We are given a grayscale image represented as a 2D integer matrix `img`. Each cell contains a pixel value. We must create a smoothed image. For every cell, compute the average of: 1. The cell itself 2. All valid neighboring cells Neighbors include all eight surrounding directions: ```text top bottom left right top-left top-right bottom-left bottom-right ``` The average is rounded down to the nearest integer. Cells outside the image boundaries are ignored. Return the resulting smoothed matrix. ## Input and Output | Item | Meaning | |---|---| | Input | A 2D integer matrix `img` | | Output | A smoothed 2D integer matrix | | Neighbor rule | Include all valid adjacent cells and the cell itself | | Averaging rule | Use floor division | Example function shape: ```python def imageSmoother(img: list[list[int]]) -> list[list[int]]: ... ``` ## Examples Consider: ```python img = [ [1, 1, 1], [1, 0, 1], [1, 1, 1], ] ``` For the center cell: ```text 0 ``` we average all 9 cells: ```text 1 + 1 + 1 1 + 0 + 1 1 + 1 + 1 ``` The sum is: ```text 8 ``` The count is: ```text 9 ``` So: ```text 8 // 9 = 0 ``` For the top-left corner: ```text 1 ``` only 4 cells are valid: ```text 1 1 1 0 ``` The sum is: ```text 3 ``` The count is: ```text 4 ``` So: ```text 3 // 4 = 0 ``` The final output is: ```python [ [0, 0, 0], [0, 0, 0], [0, 0, 0], ] ``` Another example: ```python img = [ [100, 200, 100], [200, 50, 200], [100, 200, 100], ] ``` The smoothed image becomes: ```python [ [137, 141, 137], [141, 138, 141], [137, 141, 137], ] ``` ## First Thought: Direct Simulation For every cell, we can check all neighboring positions. There are only: ```text 9 possible positions ``` including the cell itself. So for each cell: 1. Visit all neighboring offsets. 2. Ignore positions outside the matrix. 3. Compute the total sum. 4. Count how many cells were included. 5. Store: ```text sum // count ``` This is efficient because each cell only checks a constant number of neighbors. ## Key Insight The important detail is boundary handling. For a middle cell, all 9 surrounding positions exist. For an edge or corner cell, some neighbors fall outside the matrix and must be ignored. So before using a neighbor position: ```text (nr, nc) ``` we must verify: ```text 0 <= nr < rows 0 <= nc < cols ``` ## Direction Offsets We can represent all neighboring positions using row and column offsets. The offsets are: | Row offset | Column offset | |---|---| | `-1` | `-1` | | `-1` | `0` | | `-1` | `1` | | `0` | `-1` | | `0` | `0` | | `0` | `1` | | `1` | `-1` | | `1` | `0` | | `1` | `1` | For a cell: ```text (r, c) ``` the neighbor becomes: ```text (r + dr, c + dc) ``` ## Algorithm 1. Get matrix dimensions. 2. Create an output matrix. 3. For every cell: - Initialize `total = 0` - Initialize `count = 0` 4. Check all 9 neighboring offsets. 5. If the neighbor is inside bounds: - Add its value to `total` - Increase `count` 6. Store: ```python total // count ``` in the result matrix. 7. Return the result. ## Correctness For each cell `(r, c)`, the algorithm examines every possible neighboring position, including the cell itself. A neighboring position is included only if it lies inside the matrix boundaries. Therefore, the algorithm includes exactly the valid neighbors required by the problem. The variables `total` and `count` accumulate: | Variable | Meaning | |---|---| | `total` | Sum of all valid neighboring pixel values | | `count` | Number of valid neighboring cells | The algorithm stores: ```text total // count ``` which is exactly the floor of the average required by the problem statement. Since this process is applied independently to every cell, the resulting matrix is the correctly smoothed image. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(rows * cols)` | Each cell checks only 9 neighbors | | Space | `O(rows * cols)` | The output matrix is stored separately | The neighbor loop is constant size, so it does not affect asymptotic complexity. ## Implementation ```python from typing import List class Solution: def imageSmoother(self, img: List[List[int]]) -> List[List[int]]: rows = len(img) cols = len(img[0]) result = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): total = 0 count = 0 for dr in (-1, 0, 1): for dc in (-1, 0, 1): nr = r + dr nc = c + dc if 0 <= nr < rows and 0 <= nc < cols: total += img[nr][nc] count += 1 result[r][c] = total // count return result ``` ## Code Explanation We first compute the matrix dimensions: ```python rows = len(img) cols = len(img[0]) ``` Then create the output matrix: ```python result = [[0] * cols for _ in range(rows)] ``` We process every cell: ```python for r in range(rows): for c in range(cols): ``` For each cell, we track: ```python total = 0 count = 0 ``` Then we check all neighboring offsets: ```python for dr in (-1, 0, 1): for dc in (-1, 0, 1): ``` The neighbor position becomes: ```python nr = r + dr nc = c + dc ``` We only use neighbors inside the image: ```python if 0 <= nr < rows and 0 <= nc < cols: ``` Then we update the running sum and count: ```python total += img[nr][nc] count += 1 ``` Finally, we compute the floor average: ```python result[r][c] = total // count ``` After all cells are processed, we return the smoothed image. ## Testing ```python def run_tests(): s = Solution() img = [ [1, 1, 1], [1, 0, 1], [1, 1, 1], ] assert s.imageSmoother(img) == [ [0, 0, 0], [0, 0, 0], [0, 0, 0], ] img = [ [100, 200, 100], [200, 50, 200], [100, 200, 100], ] assert s.imageSmoother(img) == [ [137, 141, 137], [141, 138, 141], [137, 141, 137], ] img = [ [5], ] assert s.imageSmoother(img) == [ [5], ] img = [ [1, 2], [3, 4], ] assert s.imageSmoother(img) == [ [2, 2], [2, 2], ] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | 3×3 matrix with center `0` | Standard example | | Larger values | Confirms averaging correctness | | Single-cell image | Smallest valid input | | 2×2 matrix | Checks corner handling and boundaries |