Matrix Block Sum
Understanding the Problem
For each cell (i, j) in the matrix, we need to compute the sum of a rectangular sub-region centered at (i, j) with a "radius" of k in each direction. The block extends from row i - k to row i + k, and from column j - k to column j + k. Of course, we have to clamp these boundaries so we don't go outside the matrix.
The question is how to compute these rectangular sums efficiently. Summing up the rectangle independently for every cell repeats work, because neighboring cells share most of their block. A 2D prefix sum precomputes cumulative sums so that any rectangular sub-region sum can be answered in O(1) time with an inclusion-exclusion formula.
Key Constraints:
1 <= m, n <= 100-> The matrix has at most 100 x 100 = 10,000 cells. Brute force runs in O(m n k^2), about 10^8 operations in the worst case, which is borderline. An O(m n) solution after O(m n) preprocessing is far safer.1 <= k <= 100-> k can equal the matrix dimensions, so a block can cover the entire matrix for every cell. This rules out any assumption that blocks stay small.1 <= mat[i][j] <= 100-> All values are positive. The largest possible block sum is 100 100 100 = 10^6, well within a 32-bit integer, so no overflow concerns.
Approach 1: Brute Force
Intuition
For each cell (i, j), iterate over every cell in the block defined by [i-k, i+k] x [j-k, j+k], clamping to matrix boundaries, and sum them up. This follows the problem statement directly and computes each block independently.
Algorithm
- Create a result matrix of the same dimensions as
mat. - For each cell
(i, j), determine the block boundaries:r1 = max(0, i-k),r2 = min(m-1, i+k),c1 = max(0, j-k),c2 = min(n-1, j+k). - Iterate over all cells
(r, c)in the range[r1, r2] x [c1, c2]and accumulate the sum. - Store the sum in
answer[i][j]. - Return the result matrix.
Visualization and Code
Loading animation...
- Time Complexity: O(m n k^2). For each of the m n cells, we iterate over a block of up to (2k+1) (2k+1) cells.
- Space Complexity: O(m * n). We only use space for the output matrix.
Adjacent cells share most of their block, yet this approach recomputes the entire sum from scratch each time. The next approach precomputes cumulative sums once, then answers each block in constant time.
Approach 2: 2D Prefix Sum (Optimal)
Intuition
Build an auxiliary matrix where prefix[i][j] stores the sum of all elements in the sub-matrix from (0, 0) to (i-1, j-1). With these cumulative sums in hand, the sum of any rectangular sub-region reduces to combining four corner values.
To get the sum of the rectangle from (r1, c1) to (r2, c2):
sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
We subtract the region above and the region to the left, but that double-subtracts the top-left corner, so we add it back.
Start with the full block from (0, 0) to (r2, c2), which is prefix[r2+1][c2+1]. Subtract the strip above the target rectangle (rows 0 to r1-1), then subtract the strip to its left (columns 0 to c1-1). The overlap of those two strips, the corner region from (0,0) to (r1-1, c1-1), is subtracted twice, so add prefix[r1][c1] back once. What remains is exactly the target rectangle.
Algorithm
- Build a prefix sum matrix of size
(m+1) x (n+1), initialized to zero. The extra row and column handle boundary cases cleanly. - Fill the prefix matrix:
prefix[i+1][j+1] = mat[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]. - For each cell
(i, j), compute the block boundaries:r1 = max(0, i-k),r2 = min(m-1, i+k),c1 = max(0, j-k),c2 = min(n-1, j+k). - Use the inclusion-exclusion formula to get the block sum in O(1):
answer[i][j] = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]. - Return the result matrix.
Visualization and Code
Loading animation...
- Time Complexity: O(m n). Building the prefix sum matrix takes O(m n). Computing the answer for each of the m n cells takes O(1) per cell, for another O(m n). Total: O(m * n).
- Space Complexity: O(m n). The prefix sum matrix uses O(m n) space.