You've implemented 2D prefix sum for Range Sum Query 2D. The logic seems right. You submit.
Wrong Answer.
The test case fails with an incorrect sum. You check your formula—it looks correct. But somewhere in the inclusion-exclusion logic, there's a subtle indexing error.
Sound familiar? 2D prefix sum has twice the indexing complexity of 1D, and the inclusion-exclusion formula adds another layer of confusion. One wrong +1 or missing subtraction, and your entire solution breaks.
In this guide, you'll learn the correct inclusion-exclusion formula, why we add and subtract specific cells, visual proofs, and how to avoid the mistakes that cause wrong answers.
Common mistakes:
Correct formulas:
Building:
prefix[r][c] = (
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1] # Critical: subtract overlap
)Querying:
sum = (
prefix[row2+1][col2+1] -
prefix[row1][col2+1] -
prefix[row2+1][col1] +
prefix[row1][col1] # Critical: add back corner
)In 1D, we just add: prefix[i] = prefix[i-1] + nums[i-1]
In 2D, we're combining two overlapping rectangles, so we need to account for the overlap.
Formula:
prefix[r][c] =
matrix[r-1][c-1] + // Current cell
prefix[r-1][c] + // Rectangle above
prefix[r][c-1] - // Rectangle to the left
prefix[r-1][c-1] // Subtract overlap (counted twice)Why subtract overlap?
Visual representation:
+-------+---+
| | A |
| O +---+
| | X |
+-------+---+
O = overlap region (prefix[r-1][c-1])
A = above only (part of prefix[r-1][c])
L = left only (part of prefix[r][c-1])
X = current cell (matrix[r-1][c-1])
prefix[r-1][c] includes: O + A
prefix[r][c-1] includes: O + L
If we just add them:
matrix[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1]
= X + (O + A) + (O + L)
= X + A + L + 2O ← O is counted TWICE!
To fix, subtract O once:
= X + (O + A) + (O + L) - O
= X + A + L + O ✓Formula:
sum(row1, col1, row2, col2) =
prefix[row2+1][col2+1] - // Large rectangle from (0,0)
prefix[row1][col2+1] - // Subtract top part
prefix[row2+1][col1] + // Subtract left part
prefix[row1][col1] // Add back corner (subtracted twice)Why add back corner?
Visual representation:
+---+-------+
| C | T |
+---+-------+
| L | R |
| | |
+---+-------+
C = corner (prefix[row1][col1])
T = top part (prefix[row1][col2+1] - C)
L = left part (prefix[row2+1][col1] - C)
R = result rectangle (what we want)
prefix[row2+1][col2+1] = C + T + L + R
To isolate R:
R = (C + T + L + R) - (C + T) - (C + L) + C
= prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
Why +C at the end?
When we subtract (C + T) and (C + L), we subtract C TWICE
So we add it back once# WRONG: Missing - prefix[r-1][c-1]
for r in range(1, rows + 1):
for c in range(1, cols + 1):
prefix[r][c] = (
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1]
# BUG: Not subtracting overlap!
)matrix = [[1, 2], [3, 4]]
Building prefix (WRONG):
prefix[1][1] = 1 + 0 + 0 = 1 ✓
prefix[1][2] = 2 + 0 + 1 = 3 ✓
prefix[2][1] = 3 + 1 + 0 = 4 ✓
prefix[2][2] = 4 + 3 + 4 = 11 ❌ (should be 10)
Why wrong?
prefix[2][2] should be sum of entire matrix = 1+2+3+4 = 10
But we got 11 because we counted prefix[1][1] = 1 twice# CORRECT
for r in range(1, rows + 1):
for c in range(1, cols + 1):
prefix[r][c] = (
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1] # ✓ Subtract overlap
)
# Now:
prefix[2][2] = 4 + 3 + 4 - 1 = 10 ✓# WRONG: Missing +1 on indices
def sumRegion(self, row1, col1, row2, col2):
return (
self.prefix[row2][col2] - # Should be row2+1, col2+1
self.prefix[row1][col2] - # Should be col2+1
self.prefix[row2][col1] + # Should be row2+1
self.prefix[row1][col1]
)matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Query: sumRegion(1, 1, 2, 2) # Should return 5+6+8+9 = 28
With bug:
prefix[2][2] - prefix[1][2] - prefix[2][1] + prefix[1][1]
= 12 - 3 - 5 + 1
= 5 ❌ (should be 28)
With fix:
prefix[3][3] - prefix[1][3] - prefix[3][1] + prefix[1][1]
= 45 - 6 - 12 + 1
= 28 ✓Remember: prefix[r][c] stores sum from (0,0) to (r-1, c-1).
To include row2 and col2, we need prefix[row2+1][col2+1].
# CORRECT
def sumRegion(self, row1, col1, row2, col2):
return (
self.prefix[row2+1][col2+1] - # ✓ Include row2, col2
self.prefix[row1][col2+1] -
self.prefix[row2+1][col1] +
self.prefix[row1][col1]
)# WRONG: No padding
prefix = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
prefix[r][c] = matrix[r][c]
if r > 0:
prefix[r][c] += prefix[r-1][c]
if c > 0:
prefix[r][c] += prefix[r][c-1]
if r > 0 and c > 0:
prefix[r][c] -= prefix[r-1][c-1]Requires special cases for r=0 and c=0, making the code complex and error-prone.
# CORRECT: Pad with extra row and column
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(1, rows + 1):
for c in range(1, cols + 1):
prefix[r][c] = (
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1]
)
# No special cases needed!# WRONG: Using r, c directly
prefix[r][c] = (
matrix[r][c] + # Should be matrix[r-1][c-1]
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1]
)With padding, prefix is size (rows+1) × (cols+1), but matrix is size rows × cols.
When r=rows, matrix[r][c] is out of bounds!
# CORRECT: Offset by 1
prefix[r][c] = (
matrix[r-1][c-1] + # ✓ Offset for padding
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1]
)Matrix:
[1, 2, 3]
[4, 5, 6]
Step-by-step building prefix (with padding):
Initial:
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
prefix[1][1] = 1 + 0 + 0 - 0 = 1
[0, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 0, 0]
prefix[1][2] = 2 + 0 + 1 - 0 = 3
[0, 0, 0, 0]
[0, 1, 3, 0]
[0, 0, 0, 0]
prefix[1][3] = 3 + 0 + 3 - 0 = 6
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 0, 0, 0]
prefix[2][1] = 4 + 1 + 0 - 0 = 5
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 0, 0]
prefix[2][2] = 5 + 3 + 5 - 1 = 12
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 12, 0]
prefix[2][3] = 6 + 6 + 12 - 3 = 21
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 12, 21]
Final prefix:
[0, 0, 0, 0]
[0, 1, 3, 6]
[0, 5, 12, 21]Query: sumRegion(0, 1, 1, 2)
Rectangle: [2, 3]
[5, 6]
Expected: 2 + 3 + 5 + 6 = 16
Formula:
prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]
= prefix[2][3] - prefix[0][3] - prefix[2][1] + prefix[0][1]
= 21 - 0 - 5 + 0
= 16 ✓class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix or not matrix[0]:
self.prefix = [[]]
return
rows, cols = len(matrix), len(matrix[0])
# Pad with extra row and column
self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(1, rows + 1):
for c in range(1, cols + 1):
self.prefix[r][c] = (
matrix[r-1][c-1] + # Current cell
self.prefix[r-1][c] + # Above
self.prefix[r][c-1] - # Left
self.prefix[r-1][c-1] # Subtract overlap
)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return (
self.prefix[row2+1][col2+1] - # Large rectangle
self.prefix[row1][col2+1] - # Subtract top
self.prefix[row2+1][col1] + # Subtract left
self.prefix[row1][col1] # Add back corner
)class NumMatrix {
constructor(matrix) {
if (!matrix || !matrix.length || !matrix[0].length) {
this.prefix = [[]];
return;
}
const rows = matrix.length, cols = matrix[0].length;
this.prefix = Array(rows + 1).fill(0)
.map(() => Array(cols + 1).fill(0));
for (let r = 1; r <= rows; r++) {
for (let c = 1; c <= cols; c++) {
this.prefix[r][c] =
matrix[r-1][c-1] +
this.prefix[r-1][c] +
this.prefix[r][c-1] -
this.prefix[r-1][c-1];
}
}
}
sumRegion(row1, col1, row2, col2) {
return (
this.prefix[row2+1][col2+1] -
this.prefix[row1][col2+1] -
this.prefix[row2+1][col1] +
this.prefix[row1][col1]
);
}
}class NumMatrix {
private int[][] prefix;
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
prefix = new int[0][0];
return;
}
int rows = matrix.length, cols = matrix[0].length;
prefix = new int[rows + 1][cols + 1];
for (int r = 1; r <= rows; r++) {
for (int c = 1; c <= cols; c++) {
prefix[r][c] =
matrix[r-1][c-1] +
prefix[r-1][c] +
prefix[r][c-1] -
prefix[r-1][c-1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return
prefix[row2+1][col2+1] -
prefix[row1][col2+1] -
prefix[row2+1][col1] +
prefix[row1][col1];
}
}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]
]
obj = NumMatrix(matrix)
# Test 1: Single cell
assert obj.sumRegion(0, 0, 0, 0) == 3
# Test 2: Single row
assert obj.sumRegion(0, 0, 0, 4) == 10 # 3+0+1+4+2
# Test 3: Single column
assert obj.sumRegion(0, 0, 4, 0) == 14 # 3+5+1+4+1
# Test 4: Rectangle
assert obj.sumRegion(2, 1, 4, 3) == 8 # 2+0+1 + 1+0+1 + 0+3+0
# Test 5: Entire matrix
assert obj.sumRegion(0, 0, 4, 4) == 58If your solution fails:
Master 2D off-by-one errors with these problems:
Q: Why do we need both -prefix[r-1][c-1] when building AND +prefix[row1][col1] when querying?
A: When building, we subtract to avoid double-counting overlap. When querying, we add back because we subtracted the corner twice.
Q: How do I remember which formula is which?
A: Building: Add current + above + left - overlap
Querying: Large - top - left + corner
Q: Can I avoid padding?
A: You can, but you'll need special cases for row1=0 or col1=0, making the code more complex and error-prone.
Q: What if I get the signs wrong?
A: Trace with a 2×2 matrix manually. If your answer is too high, you're missing a subtraction. If too low, you're subtracting too much or missing an addition.
2D prefix sum off-by-one errors are subtle but avoidable with the right understanding.
Key takeaways:
The formulas:
Building:
prefix[r][c] = matrix[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1]Querying:
sum = prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]Master these formulas, and you'll never submit a wrong answer due to 2D indexing errors. For more, see 2D Prefix Sum, Off-by-One Errors, and the complete guide.
Next time you implement 2D prefix sum, remember: subtract overlap when building, add back corner when querying.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free