Show problems as
Classic problem #1314MediumArrayMatrixPrefix Sum

Matrix Block Sum

Real-world version: Neighbourhood Totals On A Sensor Panel
Tracked in this browser only
Read Matrix Block Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rectangular sensor panel is given as a grid panel, where panel[i][j] is the reading of the sensor in row i, column j. Every row of the panel has the same length.

For each sensor the technician wants the combined reading of its neighbourhood. Return a grid out of the same shape as panel, where out[i][j] is the sum of panel[r][c] over every pair (r, c) that lies inside the panel and satisfies both

  • i - reach <= r <= i + reach, and
  • j - reach <= c <= j + reach.

The sensor at (i, j) is part of its own neighbourhood. Positions that fall off the edge of the panel do not exist and add nothing, so a neighbourhood near a corner simply holds fewer sensors. reach may be larger than the panel itself.

Examples

Example 1

Input
panel = [[2,5,1],[4,3,9],[7,6,8]], reach = 1
Output
[[14, 24, 18], [27, 45, 32], [20, 37, 26]]

For the corner cell (0, 0) the neighbourhood holds rows 0 to 1 and columns 0 to 1, so its total is 2 + 5 + 4 + 3 = 14. For the middle cell (1, 1) every sensor is within reach, giving 2 + 5 + 1 + 4 + 3 + 9 + 7 + 6 + 8 = 45.

Example 2

Input
panel = [[3,1,4,1],[5,9,2,6]], reach = 1
Output
[[18, 24, 23, 13], [18, 24, 23, 13]]

Cell (0, 2) covers both rows and columns 1 to 3, so its total is 1 + 4 + 1 + 9 + 2 + 6 = 23.

Example 3

Input
panel = [[6],[1],[9],[4],[2]], reach = 1
Output
[[7], [16], [14], [15], [6]]

The panel is a single column, so each neighbourhood is just the cell together with the ones directly above and below it where they exist: cell (0, 0) gives 6 + 1 = 7 and cell (2, 0) gives 1 + 9 + 4 = 14.

Constraints

  • 1 <= panel.length <= 100
  • 1 <= panel[i].length <= 100
  • 1 <= reach <= 100
  • 1 <= panel[i][j] <= 100
  • All rows of panel have equal length.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def window_totals(panel: list[list[int]], reach: int) -> list[list[int]]:
Java
public int[][] windowTotals(int[][] panel, int reach)

More on the same topics