2D Prefix Sum
Extend prefix sums to a matrix. prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i,j). Any sub-rectangle sum can be computed in O(1) using inclusion-exclusion.
How It Works
A 2D prefix sum extends cumulative totals to matrices: prefix[i][j] stores the sum of the rectangle from the origin (0,0) to cell (i,j). It is built row by row with inclusion-exclusion — add the cell above and the cell to the left, then subtract the diagonal cell counted twice. Construction is O(m·n).
Once built, any sub-rectangle sum is four lookups: the big corner, minus the region above, minus the region to the left, plus the doubly-subtracted top-left block. That turns every rectangle query from O(m·n) into O(1), which is what makes problems like counting or maximizing submatrix sums tractable. Padding the table with an extra zero row and column removes all boundary special-casing.
Step-by-Step Visualization
Code
static int[][] build2DPrefix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] p = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
p[i][j] = matrix[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
return p;
}
// Query sum from (r1,c1) to (r2,c2):
// p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]Tips & Gotchas
Practice Problems
- 1Range Sum Query 2D - Immutable
- 2Max Sum of Rectangle No Larger Than K
- 3Number of Submatrices That Sum to Target
- 4Matrix Block Sum
About the Prefix Sum Pattern
Build an auxiliary array where each element stores the cumulative sum from the start. Then any range sum [i, j] is just prefix[j] − prefix[i−1] in O(1). Transforms repeated sum queries from O(n) to O(1) each.
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Common Array Interview Problems
- Two Sum
- Best Time to Buy & Sell Stock
- Maximum Subarray
- Merge Intervals
- Product of Array Except Self
- Container With Most Water
Frequently Asked Questions
Why does the construction formula subtract prefix[i−1][j−1]?
The rectangle above and the rectangle to the left both contain the block ending at (i−1, j−1), so adding them counts that block twice. Subtracting it once restores each cell to exactly one contribution — classic inclusion-exclusion.
How do 2D problems reduce to the 1D prefix-hashmap trick?
Fix a pair of rows, then collapse each column between them into a single value using column prefix sums. The matrix problem becomes 'count subarrays with sum K' on that 1D array, solvable with the prefix-plus-hashmap technique, giving O(m²·n) overall for target-sum submatrix counting.