Problem Breakdown
We are given a m x n matrix mat and an integer radius k. The goal is to construct a new matrix where each cell (i, j) contains the sum of all elements within distance k from it (both horizontally and vertically). This effectively requires calculating the sum of rectangular subgrids centered at every position in the output grid.
Inputs:
- A 2D integer array
mat. - An integer radius
k.
Outputs:
- A new matrix
answerwhere each cell holds the calculated block sum for its corresponding center.
Intuition
The naive approach involves iterating through every cell in the output grid and then looping over all valid neighbors within distance k to compute the sum directly. This results in a time complexity of . Given constraints where dimensions can be up to 100, this might pass but is inefficient compared to optimal solutions for larger inputs or stricter limits.
Key Insight: The problem asks for sums over rectangular regions defined by boundaries and . This maps directly to a 2D Range Sum Query. By preprocessing the matrix into a 2D Prefix Sum array (Cumulative Sum), we can calculate any subgrid sum in time using the inclusion-exclusion principle.
Approach
- Preprocessing: Create a
prefixmatrix of size . We use an extra row and column initialized to zeros to simplify boundary checks during summation queries without needing explicit clamping logic for every access in the prefix build phase, though we will clamp query bounds.prefix[i][j]stores the sum of all elements inmatfrom(0, 0)up to(i-1, j-1).
- Building Prefix Sum: Iterate through each cell (mapped to prefix indices). The value is calculated as:
- Current element + Top cumulative sum + Left cumulative sum - Diagonal overlap correction.
- Querying for Answer: For every target position
(i, j)in the output matrix:- Calculate valid row bounds clamped to matrix dimensions:
r_start = max(0, i-k),r_end = min(m-1, i+k). - Calculate valid column bounds similarly.
- Calculate valid row bounds clamped to matrix dimensions:
- Inclusion-Exclusion: Use the prefix matrix to calculate the sum of the rectangle defined by these clamped bounds in time per cell:
Complexity Analysis
- Time Complexity: . We iterate through the matrix twice: once to build the prefix sums and once to compute each answer value using constant-time queries. This is optimal since we must read every element at least once.
- Space Complexity: for storing the
prefixarray (and implicitly the output).
Solution
from typing import List
class Solution:
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
m, n = len(mat), len(mat[0])
# Create a prefix sum array with padding (m+1 x n+1).
# The extra row/col of zeros handles boundary conditions naturally.
# prefix[i][j] stores the sum from mat[0..i-1][0..j-1].
prefix = [[0] * (n + 1) for _ in range(m + 1)]
# Build the cumulative sum matrix
for i in range(1, m + 1):
row_sum = 0
for j in range(1, n + 1):
row_sum += mat[i - 1][j - 1]
prefix[i][j] = prefix[i - 1][j] + row_sum
# Initialize the answer matrix
ans = [[0] * n for _ in range(m)]
# Compute each cell's block sum using inclusion-exclusion principle
for i in range(m):
r_min, r_max = max(0, i - k), min(m - 1, i + k)
for j in range(n):
c_min, c_max = max(0, j - k), min(n - 1, j + k)
# Map matrix indices to prefix array (add 1 due to padding row/col 0)
ans[i][j] = prefix[r_max + 1][c_max + 1] \
- prefix[r_min][c_max + 1] \
- prefix[r_max + 1][c_min] \
+ prefix[r_min][c_min]
return ans
Edge Cases Handled
- k larger than matrix dimensions: The
minandmaxfunctions clamp the row/column bounds to valid indices ( or ), ensuring we never access out-of-bounds memory. This effectively sums the entire available subgrid for that cell ifkis large enough. - Single element matrices: Logic holds as loops run once, prefix array handles single values correctly (padding ensures no index errors).
- k = 0: The range becomes exactly
iandj, summing only the cell itself (handled by bounds logic where min=max=cell_index).