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.lengthn == mat[i].length1 <= m, n, K <= 1001 <= 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)
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int[][] matrixBlockSum(int[][] mat, int K) { | |
| int[][] sum = new int[mat.length][mat[0].length]; | |
| for (int r = 0; r < mat.length; r++) { | |
| for (int c = 0; c < mat[0].length; c++) { | |
| if (r == 0 && c == 0) { | |
| sum[r][c] = mat[r][c]; | |
| } else if (r == 0) { | |
| sum[r][c] = mat[r][c] + sum[r][c - 1]; | |
| } else if (c == 0) { | |
| sum[r][c] = mat[r][c] + sum [r - 1][c]; | |
| } else { | |
| sum[r][c] = mat[r][c] + sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1]; | |
| } | |
| } | |
| } | |
| int[][] ans = new int[mat.length][mat[0].length]; | |
| for (int r = 0; r < mat.length; r++) { | |
| for (int c = 0; c < mat[0].length; c++) { | |
| // bounds check on top left, bottom right | |
| int r1 = Math.max(r - K, 0); | |
| int c1 = Math.max(c - K, 0); | |
| int r2 = Math.min(mat.length - 1, r + K); | |
| int c2 = Math.min(mat[0].length - 1, c + K); | |
| ans[r][c] = sum[r2][c2] - (r1 > 0 ? sum[r1 - 1][c2] : 0) - (c1 > 0 ? sum[r2][c1 - 1] : 0) + (r1 > 0 && c1 > 0 ? sum[r1 - 1][c1 - 1] : 0); | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
