49. Range Sum Query 2D - Immutable
🔗 LeetCode Problem: 304. Range Sum Query 2D - Immutable
📊 Difficulty: Medium
🏷️ Topics: Array, Design, Matrix, Prefix Sum
Problem Statement
Given a 2D matrix matrix, handle multiple queries of the following type:
- Calculate the sum of the elements of
matrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
Implement the NumMatrix class:
NumMatrix(int[][] matrix)Initializes the object with the integer matrixmatrix.int sumRegion(int row1, int col1, int row2, int col2)Returns the sum of the elements ofmatrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.
Example 1:
Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (sum of the red rectangele)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (sum of the blue rectangle)
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -10^4 <= matrix[i][j] <= 10^4
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 10^4 calls will be made to sumRegion.
🎨 Visual Understanding
The Problem Visualized
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
Query: sumRegion(2, 1, 4, 3)
Rectangle from (2,1) to (4,3):
[3, 0, 1, 4, 2]
[5, 6, 3, 2, 1]
[1, 2, 0, 1, 5] ← row 2
[4, 1, 0, 1, 7]
[1, 0, 3, 0, 5] ← row 4
↑ ↑
col 1 col 3
Selected elements:
[2, 0, 1] (row 2, cols 1-3)
[1, 0, 1] (row 3, cols 1-3)
[0, 3, 0] (row 4, cols 1-3)
Sum = 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8
Key Observation: Extend 1D Prefix Sum to 2D
1D Prefix Sum (Problem #46):
prefixSum[i] = sum from 0 to i
Range sum = prefixSum[right] - prefixSum[left-1]
2D Prefix Sum:
prefixSum[i][j] = sum of rectangle from (0,0) to (i,j)
Visual:
(0,0) ─────────────┐
│ │
│ │
│ │
└────────── (i,j)
prefixSum[i][j] = sum of all elements in this rectangle
The 2D Prefix Sum Formula
Building prefix sum:
prefixSum[i][j] = sum of rectangle from (0,0) to (i-1,j-1)
= prefixSum[i-1][j] (rectangle above)
+ prefixSum[i][j-1] (rectangle to left)
- prefixSum[i-1][j-1] (overlap, counted twice)
+ matrix[i-1][j-1] (current cell)
Visual:
┌─────────┬──┐
│ A │ B│
├─────────┼──┤
│ C │ D│
└─────────┴──┘
A = prefixSum[i-1][j-1]
B = prefixSum[i-1][j] - A
C = prefixSum[i][j-1] - A
D = matrix[i-1][j-1]
prefixSum[i][j] = A + B + C + D
= prefixSum[i-1][j-1] + (prefixSum[i-1][j] - prefixSum[i-1][j-1])
+ (prefixSum[i][j-1] - prefixSum[i-1][j-1]) + matrix[i-1][j-1]
= prefixSum[i-1][j] + prefixSum[i][j-1]
- prefixSum[i-1][j-1] + matrix[i-1][j-1]
Query Formula (Inclusion-Exclusion Principle)
Goal: Get sum of rectangle from (row1, col1) to (row2, col2) ONLY
Let's derive this step by step with a concrete example:
Matrix:
[1 2 3 4]
[5 6 7 8]
[9 10 11 12]
[13 14 15 16]
Query: sumRegion(1, 1, 2, 2)
We want ONLY: 6 + 7 + 10 + 11 = 34
Step 1: Start with BIG rectangle from (0,0) to (2,2)
[1 2 3 ] 4 ← Include row 0, 1, 2
[5 6 7 ] 8 ← Include columns 0, 1, 2
[9 10 11 ] 12
13 14 15 16
Sum = 1+2+3+5+6+7+9+10+11 = 54
This is: prefixSum[row2+1][col2+1] = prefixSum[3][3] = 54
(Remember +1 for padding)
But we have TOO MUCH! We need to remove unwanted parts.
Step 2: Remove TOP part (rows above row1)
[1 2 3 ] 4 ← row 0 (REMOVE THIS!)
[5 6 7 ] 8 ← row 1 (keep)
[9 10 11 ] 12 ← row 2 (keep)
13 14 15 16
Remove: 1 + 2 + 3 = 6
This is: prefixSum[row1][col2+1] = prefixSum[1][3] = 6
After removal: 54 - 6 = 48
Step 3: Remove LEFT part (columns before col1)
[1 ] 2 3 4 ← Already removed, but...
[5 ] 6 7 8 ← col 0 (REMOVE THIS!)
[9 ]10 11 12
13 14 15 16
Remove: 1 + 5 + 9 = 15
BUT WAIT! The "1" was already removed in Step 2!
We're subtracting it TWICE!
This is: prefixSum[row2+1][col1] = prefixSum[3][1] = 15
After removal: 48 - 15 = 33 ❌ WRONG! (should be 34)
THE PROBLEM: Double Subtraction
The cell at (0,0) with value "1" appears in BOTH: - TOP part we removed: [1, 2, 3] - LEFT part we removed: [1, 5, 9]
So we subtracted "1" TWICE! We over-subtracted by 1.
Step 4: Add back the overlap (fix double subtraction)
[1 ] 2 3 4 ← This corner was subtracted twice!
[5 ] 6 7 8
[9 ]10 11 12
13 14 15 16
Add back: 1
This is: prefixSum[row1][col1] = prefixSum[1][1] = 1
Final: 33 + 1 = 34 ✓ CORRECT!
Visual Summary:
col1 col2
↓ ↓
┌──────┬─────────┬───┐
│ A │ B │ │ ← row1-1
├──────┼─────────┼───┤
│ C │ TARGET │ │
│ │ │ │ ← row2
└──────┴─────────┴───┘
Step 1: Get total = A + B + C + TARGET
Step 2: Subtract top = - (A + B)
Step 3: Subtract left = - (A + C)
(Now A is subtracted TWICE!)
Step 4: Add back A = + A
Result: A + B + C + TARGET - A - B - A - C + A = TARGET ✓
Final Formula:
sum = prefixSum[row2+1][col2+1] // Total: A+B+C+TARGET
- prefixSum[row1][col2+1] // Top: A+B
- prefixSum[row2+1][col1] // Left: A+C (removes A again!)
+ prefixSum[row1][col1] // Add back A (fix double removal)
Key Insight: The top-left corner (A) is in BOTH "top" and "left" rectangles, so it gets subtracted twice. We add it back once to fix this!
🎯 Approach 1: Brute Force
The Most Natural Thinking 💭
Core Logic:
For each query:
1. Loop through rows from row1 to row2
2. Loop through cols from col1 to col2
3. Sum all elements in the rectangle
Implementation
class NumMatrix {
private int[][] matrix;
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) {
for (int j = col1; j <= col2; j++) {
sum += matrix[i][j];
}
}
return sum;
}
}
⏰ Time: - Constructor: O(1) - sumRegion: O(m × n) per query (worst case entire matrix)
💾 Space: O(1) - only store original matrix
✅ Approach 2: 2D Prefix Sum (Optimal)
The Breakthrough Insight 💡
Core Logic:
Precompute 2D prefix sum:
prefixSum[i][j] = sum of rectangle from (0,0) to (i-1,j-1)
Use padding (size (m+1) × (n+1)) to avoid edge cases:
prefixSum[0][j] = 0 for all j (no rows above)
prefixSum[i][0] = 0 for all i (no cols to left)
Query in O(1) using inclusion-exclusion principle
Visual Explanation:
matrix = [
[3, 0, 1],
[5, 6, 3],
[1, 2, 0]
]
Build prefixSum (with padding):
prefixSum[0][0] = 0
prefixSum[0][1] = 0
prefixSum[0][2] = 0
prefixSum[0][3] = 0
prefixSum[1][0] = 0
prefixSum[1][1] = 0 + 0 - 0 + 3 = 3
prefixSum[1][2] = 0 + 3 - 0 + 0 = 3
prefixSum[1][3] = 0 + 3 - 0 + 1 = 4
prefixSum[2][0] = 0
prefixSum[2][1] = 3 + 0 - 0 + 5 = 8
prefixSum[2][2] = 3 + 8 - 3 + 6 = 14
prefixSum[2][3] = 4 + 14 - 3 + 3 = 18
prefixSum[3][0] = 0
prefixSum[3][1] = 8 + 0 - 0 + 1 = 9
prefixSum[3][2] = 14 + 9 - 8 + 2 = 17
prefixSum[3][3] = 18 + 17 - 14 + 0 = 21
prefixSum = [
[0, 0, 0, 0],
[0, 3, 3, 4],
[0, 8, 14, 18],
[0, 9, 17, 21]
]
Query (1, 1, 2, 2) - sum of bottom-right 2×2:
sum = prefixSum[3][3] - prefixSum[1][3] - prefixSum[3][1] + prefixSum[1][1]
= 21 - 4 - 9 + 3
= 11
Verification: 6 + 3 + 2 + 0 = 11 ✓
Implementation
class NumMatrix {
private int[][] prefixSum;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
// Padding: size (m+1) × (n+1)
prefixSum = new int[m + 1][n + 1];
// Build 2D prefix sum
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefixSum[i][j] = prefixSum[i - 1][j] // above
+ prefixSum[i][j - 1] // left
- prefixSum[i - 1][j - 1] // overlap
+ matrix[i - 1][j - 1]; // current
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
// Inclusion-exclusion principle
return prefixSum[row2 + 1][col2 + 1]
- prefixSum[row1][col2 + 1]
- prefixSum[row2 + 1][col1]
+ prefixSum[row1][col1];
}
}
⏰ Time: - Constructor: O(m × n) - build prefix sum - sumRegion: O(1) per query
💾 Space: O(m × n) - for prefix sum matrix
🔍 Step-by-Step Execution
Example: matrix = [[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]]
Initial State:
═══════════════════════════════════════════════════════════════════
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
m = 5, n = 5
BUILDING PREFIX SUM (with padding)
═══════════════════════════════════════════════════════════════════
Initialize prefixSum[6][6] with zeros:
Row 0: [0, 0, 0, 0, 0, 0]
Col 0: all zeros
Row 1 (matrix row 0):
───────────────────────────────────────────────────────────────────
prefixSum[1][1] = 0 + 0 - 0 + 3 = 3
prefixSum[1][2] = 0 + 3 - 0 + 0 = 3
prefixSum[1][3] = 0 + 3 - 0 + 1 = 4
prefixSum[1][4] = 0 + 4 - 0 + 4 = 8
prefixSum[1][5] = 0 + 8 - 0 + 2 = 10
Row 1: [0, 3, 3, 4, 8, 10]
Row 2 (matrix row 1):
───────────────────────────────────────────────────────────────────
prefixSum[2][1] = 3 + 0 - 0 + 5 = 8
prefixSum[2][2] = 3 + 8 - 3 + 6 = 14
prefixSum[2][3] = 4 + 14 - 3 + 3 = 18
prefixSum[2][4] = 8 + 18 - 4 + 2 = 24
prefixSum[2][5] = 10 + 24 - 8 + 1 = 27
Row 2: [0, 8, 14, 18, 24, 27]
Row 3 (matrix row 2):
───────────────────────────────────────────────────────────────────
prefixSum[3][1] = 8 + 0 - 0 + 1 = 9
prefixSum[3][2] = 14 + 9 - 8 + 2 = 17
prefixSum[3][3] = 18 + 17 - 14 + 0 = 21
prefixSum[3][4] = 24 + 21 - 18 + 1 = 28
prefixSum[3][5] = 27 + 28 - 24 + 5 = 36
Row 3: [0, 9, 17, 21, 28, 36]
Row 4 (matrix row 3):
───────────────────────────────────────────────────────────────────
prefixSum[4][1] = 9 + 0 - 0 + 4 = 13
prefixSum[4][2] = 17 + 13 - 9 + 1 = 22
prefixSum[4][3] = 21 + 22 - 17 + 0 = 26
prefixSum[4][4] = 28 + 26 - 21 + 1 = 34
prefixSum[4][5] = 36 + 34 - 28 + 7 = 49
Row 4: [0, 13, 22, 26, 34, 49]
Row 5 (matrix row 4):
───────────────────────────────────────────────────────────────────
prefixSum[5][1] = 13 + 0 - 0 + 1 = 14
prefixSum[5][2] = 22 + 14 - 13 + 0 = 23
prefixSum[5][3] = 26 + 23 - 22 + 3 = 30
prefixSum[5][4] = 34 + 30 - 26 + 0 = 38
prefixSum[5][5] = 49 + 38 - 34 + 5 = 58
Row 5: [0, 14, 23, 30, 38, 58]
Final prefixSum:
[0, 0, 0, 0, 0, 0]
[0, 3, 3, 4, 8, 10]
[0, 8, 14, 18, 24, 27]
[0, 9, 17, 21, 28, 36]
[0, 13, 22, 26, 34, 49]
[0, 14, 23, 30, 38, 58]
QUERY 1: sumRegion(2, 1, 4, 3)
═══════════════════════════════════════════════════════════════════
row1=2, col1=1, row2=4, col2=3
Rectangle from (2,1) to (4,3):
Row 2: [2, 0, 1]
Row 3: [1, 0, 1]
Row 4: [0, 3, 0]
Formula:
sum = prefixSum[row2+1][col2+1]
- prefixSum[row1][col2+1]
- prefixSum[row2+1][col1]
+ prefixSum[row1][col1]
sum = prefixSum[5][4]
- prefixSum[2][4]
- prefixSum[5][1]
+ prefixSum[2][1]
sum = 38 - 24 - 14 + 8 = 8 ✓
Verification: 2+0+1+1+0+1+0+3+0 = 8 ✓
QUERY 2: sumRegion(1, 1, 2, 2)
═══════════════════════════════════════════════════════════════════
row1=1, col1=1, row2=2, col2=2
Rectangle from (1,1) to (2,2):
Row 1: [6, 3]
Row 2: [2, 0]
Formula:
sum = prefixSum[3][3]
- prefixSum[1][3]
- prefixSum[3][1]
+ prefixSum[1][1]
sum = 21 - 4 - 9 + 3 = 11 ✓
Verification: 6+3+2+0 = 11 ✓
QUERY 3: sumRegion(1, 2, 2, 4)
═══════════════════════════════════════════════════════════════════
row1=1, col1=2, row2=2, col2=4
Rectangle from (1,2) to (2,4):
Row 1: [3, 2, 1]
Row 2: [0, 1, 5]
Formula:
sum = prefixSum[3][5]
- prefixSum[1][5]
- prefixSum[3][2]
+ prefixSum[1][2]
sum = 36 - 10 - 17 + 3 = 12 ✓
Verification: 3+2+1+0+1+5 = 12 ✓
═══════════════════════════════════════════════════════════════════
All queries executed in O(1) time!
═══════════════════════════════════════════════════════════════════
🔍 Edge Cases
Case 1: Single cell query
Input: sumRegion(0, 0, 0, 0)
Output: matrix[0][0]
Case 2: Entire matrix
Input: sumRegion(0, 0, m-1, n-1)
Output: Sum of all elements
Case 3: Single row
Input: sumRegion(2, 1, 2, 4)
Output: Sum of row 2, columns 1-4
Case 4: Single column
Input: sumRegion(1, 2, 4, 2)
Output: Sum of column 2, rows 1-4
Case 5: All zeros
Input: matrix = [[0,0],[0,0]]
Output: All queries return 0
Case 6: Negative numbers
Input: matrix = [[-1, 2], [3, -4]]
sumRegion(0, 0, 1, 1): -1+2+3-4 = 0
Case 7: 1×1 matrix
Input: matrix = [[5]]
sumRegion(0, 0, 0, 0): 5
Case 8: Large rectangle
Input: Very large query covering most of matrix
Output: Computed in O(1) time
Common Mistakes
Mistake 1: Not using padding
❌ Wrong:
prefixSum = new int[m][n];
// Need complex edge case handling
✓ Right:
prefixSum = new int[m + 1][n + 1];
// Padding avoids edge cases
Reason: Padding makes formula work for all cases
Mistake 2: Wrong prefix sum formula
❌ Wrong:
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] + matrix[i][j];
// Forgot to subtract overlap
✓ Right:
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1]
- prefixSum[i-1][j-1] + matrix[i-1][j-1];
Reason: Overlap counted twice, must subtract
Mistake 3: Wrong query formula
❌ Wrong:
return prefixSum[row2][col2] - prefixSum[row1][col1];
// Missing terms
✓ Right:
return prefixSum[row2+1][col2+1]
- prefixSum[row1][col2+1]
- prefixSum[row2+1][col1]
+ prefixSum[row1][col1];
Reason: Must use inclusion-exclusion principle
Mistake 4: Index offset errors
❌ Wrong:
prefixSum[i][j] = ... + matrix[i][j];
// Wrong matrix index with padding
✓ Right:
prefixSum[i][j] = ... + matrix[i-1][j-1];
Reason: prefixSum is padded, matrix is not
Mistake 5: Not handling empty matrix
❌ Wrong:
// Assume matrix is non-empty
✓ Right:
if (matrix.length == 0 || matrix[0].length == 0) return;
Reason: Edge case handling
Mistake 6: Adding instead of subtracting in query
❌ Wrong:
return prefixSum[row2+1][col2+1]
+ prefixSum[row1][col2+1] // Should subtract
+ prefixSum[row2+1][col1] // Should subtract
...
✓ Right:
return prefixSum[row2+1][col2+1]
- prefixSum[row1][col2+1]
- prefixSum[row2+1][col1]
+ prefixSum[row1][col1];
Reason: Inclusion-exclusion requires subtraction
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Brute Force
Constructor: O(1)
Query: O(m × n)
Space: O(1)
Use: Only for understanding
Approach 2: 2D Prefix Sum (RECOMMENDED)
Constructor: O(m × n)
Query: O(1)
Space: O(m × n)
Use: Optimal for multiple queries
🔑 The Core Insight
2D Prefix Sum Extension:
═══════════════════════════════════════════════════════════════
1D Prefix Sum:
prefixSum[i] = sum from 0 to i
Range sum = prefixSum[right] - prefixSum[left-1]
2D Prefix Sum:
prefixSum[i][j] = sum of rectangle from (0,0) to (i-1,j-1)
Building Formula:
═══════════════════════════════════════════════════════════════
prefixSum[i][j] = prefixSum[i-1][j] (above)
+ prefixSum[i][j-1] (left)
- prefixSum[i-1][j-1] (overlap, counted twice)
+ matrix[i-1][j-1] (current cell)
Visual:
┌─────┬──┐
│ A │ B│
├─────┼──┤
│ C │ D│
└─────┴──┘
D = current cell
A = overlap (counted in both B and C)
Total = A + B + C + D
= (A+B) + (A+C) - A + D
= above + left - overlap + current
Query Formula (Inclusion-Exclusion):
═══════════════════════════════════════════════════════════════
sum(row1, col1, row2, col2)
= prefixSum[row2+1][col2+1] (entire bottom-right)
- prefixSum[row1][col2+1] (subtract above)
- prefixSum[row2+1][col1] (subtract left)
+ prefixSum[row1][col1] (add back overlap)
Visual:
col1 col2
┌─────┬──────┬───┐
│ A │ B │ │ ← row1
├─────┼──────┼───┤
│ C │TARGET│ │
└─────┴──────┴───┘ ← row2
TARGET = (A+B+C+TARGET) - (A+B) - (A+C) + A
Padding Technique:
═══════════════════════════════════════════════════════════════
Use (m+1) × (n+1) array:
- Row 0 and Column 0 are all zeros
- Avoids edge case checks
- Makes formula work universally
Without padding: Need to check if i=0 or j=0
With padding: Formula always works!
Time Complexity Analysis:
═══════════════════════════════════════════════════════════════
Build: O(m × n) - process each cell once
Query: O(1) - simple arithmetic
For q queries:
Brute force: O(q × m × n)
Prefix sum: O(m × n + q)
Huge improvement for large q!
Space Complexity:
═══════════════════════════════════════════════════════════════
Extra space: O(m × n) for prefix sum array
Worth it for O(1) queries!
🎯 Pattern Recognition
Problem Type: 2D Range Query with Preprocessing
Core Pattern: 2D Prefix Sum
When to Apply:
✓ Multiple range sum queries on 2D matrix
✓ Matrix doesn't change (immutable)
✓ Need O(1) query time
✓ Can afford O(m×n) preprocessing
✓ Can afford O(m×n) extra space
Recognition Keywords:
- "2D matrix" or "grid"
- "Multiple queries"
- "Range sum" or "rectangle sum"
- "Immutable"
- "Submatrix sum"
Relationship to 1D:
┌────────────────────────────────────────────┐
│ 1D Prefix Sum (Problem #46) │
│ - Linear array │
│ - prefixSum[i] = sum to i │
│ - Query: O(1) subtraction │
│ │
│ 2D Prefix Sum (This Problem) │
│ - Matrix │
│ - prefixSum[i][j] = sum to (i,j) │
│ - Query: O(1) inclusion-exclusion │
└────────────────────────────────────────────┘
Extension Pattern:
1D → 2D → 3D (same principle!)
Related Problems:
- Range Sum Query - Immutable (LC 303) - 1D version
- Matrix Block Sum (LC 1314)
- Maximal Square (LC 221)
🧠 Interview Strategy
Step 1: "Multiple range sum queries on 2D matrix"
Step 2: "Extend 1D prefix sum to 2D"
Step 3: "prefixSum[i][j] = sum of rectangle (0,0) to (i,j)"
Step 4: "Build: include above, left, subtract overlap, add current"
Step 5: "Query: inclusion-exclusion principle"
Step 6: "Use padding to avoid edge cases"
Step 7: "O(m×n) build, O(1) query, O(m×n) space"
Key Points to Mention:
- Recognize 2D extension of 1D prefix sum
- Use padding for cleaner code
- Build formula: above + left - overlap + current
- Query formula: total - above - left + overlap
- Inclusion-exclusion principle
- Index offset: prefixSum is padded, matrix is not
- Build time: O(m × n)
- Query time: O(1)
- Space: O(m × n)
- Much better for multiple queries
Why Padding?
"I'll use a (m+1)×(n+1) array with the first row and
column as zeros. This padding eliminates edge case
checks and makes the formula work uniformly for all
queries, including those at boundaries."
The Formula Explanation:
"To build the prefix sum, I include the rectangle above,
the rectangle to the left, subtract their overlap (counted
twice), then add the current cell. For queries, I use
inclusion-exclusion: take the total rectangle, subtract
unwanted parts, and add back what was subtracted twice."
This is the 2D version of a classic pattern! 🏆
📝 Quick Revision Notes
🎯 Core Concept:
2D prefix sum = sum of rectangle from (0,0) to (i,j). Build: above + left - overlap + current. Query: total - above - left + overlap (inclusion-exclusion). Use padding!
⚡ Quick Implementation:
class NumMatrix {
int[][] prefixSum;
public NumMatrix(int[][] a) {
int rows = a.length;
int cols = a[0].length;
prefixSum = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
// Simple observation by checking the prefixsum
// matrix that is calculated manually.
// current element = (prev_row + prev_col) - (prev_adj_diag_cell) + curr
// Why remove prev_adj_diag_cell? overlap caused by prev_row and prev_col cells
prefixSum[i][j] = prefixSum[i - 1][j]
+ prefixSum[i][j - 1]
- prefixSum[i - 1][j - 1]
+ a[i - 1][j - 1];
}
}
}
public int sumRegion(int r1, int c1, int r2, int c2) {
// Simple observation again
// Normally we need to return existing (r2, c2) - ignore +1 for now
// remove prev row: (r1, c2)
// remove prev col: (r2, c1)
// add back the overlap
return prefixSum[r2 + 1][c2 + 1]
- prefixSum[r1][c2 + 1]
- prefixSum[r2 + 1][c1]
+ prefixSum[r1][c1];
}
}
class Test {
public static void main(String[] args) {
Test t = new Test();
t.test();
}
private void test() {
NumMatrix numMatrix = new NumMatrix(
new int[][] { { 3, 0, 1, 4, 2 }, { 5, 6, 3, 2, 1 }, { 1, 2, 0, 1, 5 }, { 4, 1, 0, 1, 7 }, { 1, 0, 3, 0, 5 } });
System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
System.out.println(numMatrix.sumRegion(1, 2, 2, 4));
}
}
🔑 Key Insights:
- Pattern: 2D extension of 1D prefix sum
- prefixSum[i][j]: Sum of rectangle (0,0) to (i-1,j-1)
- Padding: (m+1)×(n+1) array, first row/col = 0
- Build: above + left - overlap + current
- Query: total - above - left + overlap
- Index offset: prefixSum uses i,j but matrix uses i-1,j-1
- Inclusion-exclusion: Add total, subtract unwanted, add back overlap
- Build time: O(m × n) - one pass
- Query time: O(1) - four array accesses
- Space: O(m × n) - prefix sum array
🎪 Memory Aid:
"Above + Left - Overlap + Current! Total - Above - Left + Overlap!"
Think: "2D = same as 1D but TWO dimensions!"
💡 The Visual Formula:
Building:
┌─────┬──┐
│ A │ B│ A = overlap
├─────┼──┤ B = above only
│ C │ D│ C = left only
└─────┴──┘ D = current
prefixSum[i][j] = A + B + C + D
= (A+B) + (A+C) - A + D
= above + left - overlap + current
Querying:
┌────┬─────┬──┐
│ A │ B │ │
├────┼─────┼──┤
│ C │ TGT │ │
└────┴─────┴──┘
TARGET = (A+B+C+TGT) - (A+B) - (A+C) + A
= total - above - left + overlap
🔥 Why This Works:
Inclusion-Exclusion Principle:
- Start with total rectangle
- Subtract what's above target
- Subtract what's left of target
- Add back overlap (subtracted twice)
Result: Exactly the target rectangle!
⚠️ Critical Details:
1. Use padding: (m+1) × (n+1) not m × n
2. Index offset: prefixSum[i][j] uses matrix[i-1][j-1]
3. Query offset: Add 1 to row2 and col2
4. Don't forget: Subtract overlap when building
5. Don't forget: Add overlap when querying
Related Patterns
- Range Sum Query - Immutable (LC 303) - 1D version
- Matrix Block Sum (LC 1314)
- Maximal Square (LC 221)
- Product of Array Except Self (LC 238) - Different operation
Happy practicing! 🎯