Matrix Block Sum (2D Prefix Sum) Visualization & Animation

Computes block sums for every cell in a matrix using 2D prefix sums and the inclusion-exclusion formula; O(m×n).

## What is it? Given a matrix and an integer `k`, compute a new matrix where each cell `result[i][j]` is the sum of all cells in the original matrix within the block defined by rows `[i-k, i+k]` and columns `[j-k, j+k]`. ## How it works 1. Build a 2D prefix sum matrix `prefix[i][j]` = sum of all elements in the rectangle from `(0,0)` to `(i,j)` 2. For each cell `(i,j)`, compute the block sum using the 2D prefix sum formula: ``` blockSum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] ``` where `r1 = max(0, i-k)`, `r2 = min(m-1, i+k)`, `c1 = max(0, j-k)`, `c2 = min(n-1, j+k)` ## When to use - 2D range sum queries - Image blurring / box filter operations - Any problem computing aggregate values over rectangular windows in a matrix ## Key Points - O(m*n) preprocessing, O(1) per query - Inclusion-exclusion principle for 2D rectangles - Boundary clamping (`max(0, i-k)`) handles edges where the block extends beyond the matrix

Category: algorithms

Difficulty: intermediate

  • prefix-sum

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Matrix Block Sum (2D Prefix Sum)

intermediate

Computes block sums for every cell in a matrix using 2D prefix sums and the inclusion-exclusion formula; O(m×n).

GFGLeetCode
Input mat
1
2
3
4
5
6
7
8
9
0
1
2
Prefix P
0
0
0
0
0
0
0
0
0
0
1
2
Answer
0
0
0
0
0
0
0
0
0
0
1
2
Current cell (being computed)
mat input cells
Prefix P — filled
Prefix P — source / corner
Prefix P — empty
Answer — filled / window
Answer — empty
Start: create a 3×3 prefix matrix P (same size as mat) — all zeros for now.