Neighbourhood Totals
MediumMatrix
Problem
A city planner has an m × n grid where grid[r][c] is the population of one block. For every block, she wants the total population living within radius blocks of it in both directions: all blocks (i, j) with |i - r| ≤ radius and |j - c| ≤ radius that lie inside the city.
Return an m × n grid of these totals.
Example 1
- Input:
- grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], radius = 1
- Output:
- [[12, 21, 16], [27, 45, 33], [24, 39, 28]]
Block (0, 0) sees the 2 × 2 corner 1 + 2 + 4 + 5 = 12; the centre sees all nine blocks, 45.
Example 2
- Input:
- grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], radius = 2
- Output:
- [[45, 45, 45], [45, 45, 45], [45, 45, 45]]
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ radius ≤ 200
- -1000 ≤ grid[i][j] ≤ 1000
Hint
Show the first hint
Each answer is the sum of a rectangle. What lets you sum any rectangle in O(1)?
Walkthrough
How to approach it
01Clarify before coding
- Is the window square (Chebyshev distance), not a diamond? Yes, |i - r| ≤ radius and |j - c| ≤ radius.
- What about blocks outside the city? They are simply not counted.
- Can radius exceed the grid size? Yes; the window then covers everything.
02Brute force
For each block, loop over its whole window and add up the populations.
Cost: O(m · n · (2·radius + 1)²): for 200 × 200 with radius 200 that is around 6 · 10^9 additions.
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.