1314. Matrix Block Sum

-

https://leetcode.com/problems/matrix-block-sum/

Given a m * 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
---
Intuition
Similar to prefix sum for 1D, compute prefix sum for 2D array

Prevent double counting
sum[r][c] = mat[r][c] + sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1]

With prefix sum, calculate boundaries of box, keep bounds check
r1 = max(r - k, 0)
c1 = max(c - k, 0)

r2 = min(r + k, R)
c2 = min(c + k, C)

with bounds check
ans[r][c] = sum[r2][c2] - sum[r1 - 1][c2] - sum[r2][c1 - 1] + sum[r1 - 1][c1 - 1]
---
Time - O(R * C)
Space - O(R * C)
---



---