205. Neighbourhood Sums
A weather map is a grid of readings grid. For a radius k, the neighbourhood of the cell at row i, column j is every cell at row r and column c with i - k <= r <= i + k and j - k <= c <= j + k that actually lies inside the grid. Near an edge the neighbourhood is simply cut off.
Build a grid answer of the same size where answer[i][j] is the sum of all readings in the neighbourhood of (i, j), and return it. The grid can have up to 250,000 cells and k can be large, so adding up each neighbourhood cell by cell will be too slow.
Example 1
- Input:
- grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
- Output:
- [[12,21,16],[27,45,33],[24,39,28]]
- Explanation:
For the centre cell the neighbourhood is the whole grid: 45. For the corner (0,0) it is the top-left 2x2 block: 1+2+4+5 = 12.
Example 2
- Input:
- grid = [[5,1],[2,7]], k = 1
- Output:
- [[15,15],[15,15]]
- Explanation:
With k = 1 every cell's neighbourhood covers the whole 2x2 grid, so every answer is 15.
Example 3
- Input:
- grid = [[3,4,5,6]], k = 2
- Output:
- [[12,18,18,15]]
- Explanation:
A single row: cell 0 sees columns 0 to 2 (12), cell 1 sees 0 to 3 (18), cell 2 sees 0 to 3 (18), cell 3 sees columns 1 to 3 (15).
Constraints
1 ≤ grid.length, grid[0].length ≤ 500
0 ≤ grid[i][j] ≤ 100
1 ≤ k ≤ 500
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(m × n)
- Space
- O(m × n)