{x}
blog image

Matrix Block Sum

Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:

  • i - k <= r <= i + k,
  • j - k <= c <= j + k, and
  • (r, c) is a valid position in the matrix.

 

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

Solution Explanation: 1314. Matrix Block Sum

This problem asks to calculate the sum of elements within a k x k block centered at each cell in a given matrix. The optimal solution utilizes a two-dimensional prefix sum technique for efficient computation.

Algorithm:

  1. Prefix Sum Matrix: Create a prefix sum matrix s. s[i][j] stores the sum of all elements in the submatrix from (0,0) to (i-1, j-1). This is calculated iteratively:

    s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]

    The subtraction of s[i-1][j-1] corrects for double-counting the overlapping region.

  2. Querying the Sum: To find the sum of elements in a submatrix with top-left corner (x1, y1) and bottom-right corner (x2, y2), use the following formula:

    sum = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]

  3. Iterate and Calculate: Iterate through each cell (i, j) of the input matrix mat. For each cell:

    • Determine the top-left (x1, y1) and bottom-right (x2, y2) coordinates of the k x k block centered at (i, j), handling boundary conditions (making sure you don't go beyond matrix bounds).
    • Use the prefix sum formula to efficiently calculate the sum of elements within this k x k block.
    • Store the result in the corresponding cell of the output matrix answer.

  4. Return: Return the answer matrix.

Time and Space Complexity:

  • Time Complexity: O(mn) - The algorithm iterates through the matrix twice: once to build the prefix sum matrix and once to calculate the block sums. The prefix sum calculation and block sum calculation are both O(mn) operations.

  • Space Complexity: O(m*n) - The space complexity is dominated by the prefix sum matrix s, which has the same dimensions as the input matrix.

Code Examples:

The code examples provided in the previous response demonstrate this algorithm in multiple languages (Python, Java, C++, Go, TypeScript). Each implementation follows the same algorithmic steps outlined above. The key difference lies in the syntax and data structure handling specific to each language. For example, Python uses list comprehension for creating the prefix sum matrix, whereas Java utilizes nested loops and array initialization. However, the core logic of the algorithm remains consistent.