Domain 2MediumMEDIUM

Matrix Block Sum

Compute block sums for a matrix using 2D prefix sums to achieve O(1) query time per cell, resulting in an overall optimal O(m*n) complexity.

Domain: medium•Updated: 2026-09-14
#Prefix Sums#2D Array#O(m*n)#Space Optimization

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 answer where 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 O(m⋅n⋅k2)O(m \cdot n \cdot k^2). 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 (rstart,cstart)(r_{start}, c_{start}) and (rend,cend)(r_{end}, c_{end}). 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 O(1)O(1) time using the inclusion-exclusion principle.

Approach

  1. Preprocessing: Create a prefix matrix of size (m+1)×(n+1)(m+1) \times (n+1). 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 in mat from (0, 0) up to (i-1, j-1).
  2. Building Prefix Sum: Iterate through each cell (r,c)(r, c) (mapped to prefix indices). The value is calculated as:
    • Current element + Top cumulative sum + Left cumulative sum - Diagonal overlap correction.
  3. 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.
  4. Inclusion-Exclusion: Use the prefix matrix to calculate the sum of the rectangle defined by these clamped bounds in O(1)O(1) time per cell: Sum=P(rend+1,cend+1)−P(rstart,cend+1)−P(rend+1,cstart)+P(rstart,cstart)Sum = P(r_{end}+1, c_{end}+1) - P(r_{start}, c_{end}+1) - P(r_{end}+1, c_{start}) + P(r_{start}, c_{start})

Complexity Analysis

  • Time Complexity: O(m⋅n)O(m \cdot n). 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: O(m⋅n)O(m \cdot n) for storing the prefix array (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 min and max functions clamp the row/column bounds to valid indices (00 or m/n−1m/n - 1), ensuring we never access out-of-bounds memory. This effectively sums the entire available subgrid for that cell if k is 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 i and j, summing only the cell itself (handled by bounds logic where min=max=cell_index).