[Prefix Sum] Matrix Block Sum

[sudosf]

Problem

Given an m x n matrix and integer k, return a matrix answer where answer[i][j] is the sum of all elements in the rectangle defined by (i-k, j-k) to (i+k, j+k), clamped to matrix boundaries.

References

• LeetCode: https://leetcode.com/problems/matrix-block-sum/
• GFG: https://www.geeksforgeeks.org/problems/2d-submatrix-sum-queries/1
• Sheet: https://www.risingbrain.org/sheet#array (Prefix Sum Pattern: Two Pointers (Arrays) #3)
• Parent: Pattern: Prefix Sum (Arrays) #51

Difficulty

🟡 Medium

Companies

Amazon, Google, Flipkart

Notes

Language: Java
2D prefix sum. prefix[i][j] = sum of all elements in rectangle (0,0) to (i-1,j-1).
Rectangle sum formula: prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1].