Soften the Image
EasyMatrix
Problem
A photo filter softens a greyscale image stored as an m × n grid of brightness values. Each output pixel is the average of the input pixel and its up to eight neighbours (the 3 × 3 block centred on it, clipped at the image border), rounded down to an integer.
Return the softened image. Every output pixel must be computed from the original image, not from already softened values.
Example 1
- Input:
- image = [[100, 200, 100], [200, 50, 200], [100, 200, 100]]
- Output:
- [[137, 141, 137], [141, 138, 141], [137, 141, 137]]
Corner: (100 + 200 + 200 + 50) / 4 = 137.5 → 137. Edge: 850 / 6 → 141. Centre: 1250 / 9 → 138.
Example 2
- Input:
- image = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
- Output:
- [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ image[i][j] ≤ 255
Hint
Show the first hint
How many cells are in the 3 × 3 block around a corner pixel? An edge pixel? An interior pixel?
Walkthrough
How to approach it
01Clarify before coding
- How is the average rounded? Down, to an integer.
- Do neighbours wrap around? No, the block is clipped at the border, so corners average 4 pixels and edges 6.
- May I write into the input? Only if originals are preserved; a fresh output grid is simplest.
02Brute force
The direct approach is already the right one: for each pixel, sum its clipped 3 × 3 block and divide by the number of cells in it.
Cost: O(9 · m · n) time and O(m · n) for the output. A 2-D prefix sum would make larger blocks O(1) each, but for 3 × 3 it is not needed.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.