We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Matrix Block Sum

Number: 1242

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n matrix mat and an integer k, return a matrix answer where each element answer[i][j] is the sum of all elements mat[r][c] such that r and c satisfy: i - k <= r <= i + k, j - k <= c <= j + k, and (r, c) is within the bounds of the matrix.

Key Insights

  • Brute-force summing every block for each element is inefficient for larger matrices.
  • Using a prefix sum (cumulative sum) matrix greatly optimizes the process.
  • With a prefix sum matrix, we can compute the sum of any submatrix in constant time.
  • Boundary management is crucial since the k-neighborhood may extend beyond the matrix edges.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

We compute a prefix sum matrix where each element at (i, j) represents the sum of all elements in mat from (0, 0) to (i, j). With the prefix sum matrix, the sum of any submatrix defined by its corners can be efficiently computed using the inclusion-exclusion principle. For each element in the result matrix, the boundaries of the submatrix are determined by the limits imposed by k and the matrix size. This approach ensures that each matrix cell’s block sum is calculated in constant time after an initial O(m * n) preprocessing step for building the prefix sum matrix.

Code Solutions

# Python solution using prefix sum
def matrixBlockSum(mat, k):
    # dimensions of the matrix
    m = len(mat)
    n = len(mat[0])
    
    # create a prefix sum matrix with extra row and column for easier calculations
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build prefix sum matrix
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
    
    # function to get sum of submatrix from (r1, c1) to (r2, c2) inclusive
    def get_sum(r1, c1, r2, c2):
        return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
    
    # Build result matrix
    result = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            # Determine block boundaries considering matrix limits
            r1 = max(0, i - k)
            c1 = max(0, j - k)
            r2 = min(m - 1, i + k)
            c2 = min(n - 1, j + k)
            result[i][j] = get_sum(r1, c1, r2, c2)
    return result

# Example usage:
# print(matrixBlockSum([[1,2,3],[4,5,6],[7,8,9]], 1))
← Back to All Questions