If you want to compute the sum 0..i = nums[0] + ... + nums[i] (inclusive) or other sums, you can use the prefix sum as follows.
n is nums’s size. prefix and postfix have size n+1.
[1, 3, 7, 10, 2 ]
[0 1 4 11 21 23] sum 0..i = prefix[i+1]
[23 22 19 12 2 0] sum i..n-1 = postfix[i]
Range Queries
sum L..R = sum 0..R - sum 0..L-1 = prefix[R+1] - prefix[L]
sum L..R = sum L..n-1 - sum R+1..n-1 = postfix[L] - postfix[R+1]
Constructing Prefix and Postfix
prefix = [0] * (n + 1)
# prefix[0] = 0 (base case)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
postfix = [0] * (n + 1)
# postfix[n] = 0 (base case)
for i in range(n - 1, -1, -1):
postfix[i] = postfix[i + 1] + nums[i]
def range_left(L, R):
return prefix[R + 1] - prefix[L]
def range_right(L, R):
return postfix[L] - postfix[R + 1]
To memorize:
For each num in nums, we map their inclusive sum into prefix and postfix as follows:
for i in range(n): # for each num in nums
prefix[i+1] <-- ... nums[i]
for i in range(n-1,-1,-1): # for each num in nums
postfix[i] <-- ... nums[i]
Subarray Sum Equals K 🔗
“Count the number of subarrays whose elements sum to k.”
The brute force would check all pairs (l, r) — O(n²). The key insight: sum(nums[l..r]) = prefix[r+1] - prefix[l] = k means we’re looking for prefix[l] = prefix[r+1] - k. So at each index, we check whether we’ve seen that prefix sum before using a hashmap.
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
current_sum = 0
prefix_counts = {0: 1} # the leading zero — prefix[0] = 0
for num in nums:
current_sum += num
count += prefix_counts.get(current_sum - k, 0)
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
return count
- Time Complexity: O(n)
- Space Complexity: O(n)
Note that prefix_counts = {0: 1} serves the same role as the leading zero in the prefix array — it handles the case where a subarray starting at index 0 sums to k.
Product of Array Except Self 🔗
The same idea works with multiplication. Instead of prefix sums, build prefix products and suffix products:
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [1] * n
# Prefix pass: result[i] = product of nums[0..i-1]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Suffix pass: multiply by product of nums[i+1..n-1]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
- Time Complexity: O(n)
- Space Complexity: O(1) (output array doesn’t count)
2D Prefix Sum
The same template extends to matrices. Build a 2D prefix sum where prefix[i][j] is the sum of the submatrix from (0,0) to (i-1, j-1):
rows, cols = len(matrix), len(matrix[0])
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(rows):
for j in range(cols):
prefix[i+1][j+1] = (matrix[i][j]
+ prefix[i][j+1]
+ prefix[i+1][j]
- prefix[i][j])
Query any submatrix sum from (r1, c1) to (r2, c2) in O(1):
def region_sum(r1, c1, r2, c2):
return (prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1])
This is inclusion-exclusion: add the full rectangle, subtract the two overcounted strips, add back the doubly-subtracted corner. The n+1 sizing with a zeroed border again eliminates bounds checking.