Prefix Sum Interview Patterns
Prefix sums transform range sum queries from O(n) to O(1) after O(n) preprocessing. They also underlie subarray sum problems, equilibrium index, and 2D range queries. A fundamental technique used in almost every array interview problem.
1D Prefix Sum
def build_prefix(nums: list[int]) -> list[int]:
prefix = [0] * (len(nums) + 1) # prefix[0] = 0
for i, n in enumerate(nums):
prefix[i + 1] = prefix[i] + n
return prefix
def range_sum(prefix: list[int], l: int, r: int) -> int:
"""Sum of nums[l..r] inclusive (0-indexed)."""
return prefix[r + 1] - prefix[l]
# Build O(n), query O(1)
Pattern 1: Subarray Sum Equals K (LeetCode 560)
from collections import defaultdict
def subarray_sum(nums: list[int], k: int) -> int:
count = 0
prefix = 0
seen = defaultdict(int)
seen[0] = 1 # empty prefix sums to 0
for n in nums:
prefix += n
count += seen[prefix - k] # how many times prefix - k appeared
seen[prefix] += 1
return count
# Key insight: sum(l..r) = prefix[r] - prefix[l-1] = k
# => prefix[r] - k = prefix[l-1]
# O(n) time, O(n) space
Pattern 2: Continuous Subarray Sum (LeetCode 523)
def check_subarray_sum(nums: list[int], k: int) -> bool:
"""Does any subarray of length >= 2 have sum divisible by k?"""
seen = {0: -1} # remainder -> first index
prefix = 0
for i, n in enumerate(nums):
prefix = (prefix + n) % k
if prefix in seen:
if i - seen[prefix] >= 2:
return True
else:
seen[prefix] = i
return False
# Insight: sum(l..r) % k == 0 iff prefix[r] % k == prefix[l-1] % k
Pattern 3: Longest Subarray with Sum <= K (Sliding Window + Prefix)
def longest_subarray_sum_at_most_k(nums: list[int], k: int) -> int:
prefix = 0
max_len = 0
min_prefix = {0: -1} # prefix_sum -> earliest index
for i, n in enumerate(nums):
prefix += n
target = prefix - k
# Binary search on sorted prefix sums (or use monotone deque)
# For non-negative nums: sliding window is cleaner
for j, p in min_prefix.items():
if p <= target:
max_len = max(max_len, i - p)
min_prefix[prefix] = min(min_prefix.get(prefix, i), i)
return max_len
Pattern 4: Equilibrium Index
def equilibrium_index(nums: list[int]) -> int:
total = sum(nums)
left = 0
for i, n in enumerate(nums):
# left sum = left; right sum = total - left - nums[i]
if left == total - left - n:
return i
left += n
return -1
Pattern 5: Product of Array Except Self (LeetCode 238)
def product_except_self(nums: list[int]) -> list[int]:
n = len(nums)
result = [1] * n
# Left prefix products
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right suffix products (multiply into result in-place)
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
# O(n) time, O(1) extra space (output array not counted)
Pattern 6: Subarray with Equal 0s and 1s (LeetCode 525)
def find_max_length(nums: list[int]) -> int:
"""Longest subarray with equal 0s and 1s."""
# Replace 0 with -1; find longest subarray with sum = 0
seen = {0: -1}
prefix = 0
max_len = 0
for i, n in enumerate(nums):
prefix += 1 if n else -1
if prefix in seen:
max_len = max(max_len, i - seen[prefix])
else:
seen[prefix] = i
return max_len
2D Prefix Sum
def build_2d_prefix(matrix: list[list[int]]) -> list[list[int]]:
rows, cols = len(matrix), len(matrix[0])
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])
return prefix
def range_sum_2d(prefix, r1, c1, r2, c2) -> int:
"""Sum of matrix[r1..r2][c1..c2] (0-indexed)."""
return (prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1])
Prefix Sum Decision Guide
| Problem signal | Technique |
|---|---|
| Range sum query (static array) | 1D prefix sum, O(1) query |
| Subarray sum = K | Prefix sum + hashmap of seen sums |
| Subarray sum divisible by K | Prefix sum modulo K + hashmap |
| Longest subarray with property | Prefix sum + hashmap (earliest index per sum) |
| Equal 0s and 1s (or X and Y) | Map 0→-1, find subarray with sum=0 |
| Product of array except self | Left prefix product × right suffix product |
| Matrix region sum query | 2D prefix sum, O(1) query |
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is a prefix sum and when should I use it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A prefix sum array stores cumulative sums: prefix[i] = sum of arr[0..i-1]. Range sum queries become O(1): sum(l..r) = prefix[r+1] – prefix[l]. Build in O(n), answer unlimited queries in O(1). Use prefix sums whenever you see range sum queries, subarray sum = K, or need to check if any subarray satisfies a sum condition.”
}
},
{
“@type”: “Question”,
“name”: “How do you use prefix sums with a hashmap to solve subarray sum = K?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Maintain a running prefix sum and a hashmap of {prefix_sum: count}. For each position, check if (current_prefix – K) exists in the map — if so, there are that many subarrays ending here with sum K. Add current_prefix to the map. Key insight: sum(l..r) = prefix[r] – prefix[l-1] = K, so prefix[l-1] = prefix[r] – K. Time O(n), Space O(n).”
}
},
{
“@type”: “Question”,
“name”: “How do you find the longest subarray with equal 0s and 1s?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Replace 0 with -1, then find the longest subarray with sum = 0. Use a hashmap of {prefix_sum: first_index_seen}. When the same prefix sum appears again at index j, the subarray from (first_seen + 1) to j has sum = 0. Track the maximum length. Initialize with {0: -1} to handle subarrays starting at index 0.”
}
},
{
“@type”: “Question”,
“name”: “How does the 2D prefix sum work for matrix range queries?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “prefix[r][c] = sum of all elements in the rectangle from (0,0) to (r-1,c-1). Update formula: prefix[r][c] = matrix[r-1][c-1] + prefix[r-1][c] + prefix[r][c-1] – prefix[r-1][c-1] (inclusion-exclusion). Range query for rectangle (r1,c1) to (r2,c2): prefix[r2+1][c2+1] – prefix[r1][c2+1] – prefix[r2+1][c1] + prefix[r1][c1]. O(1) per query after O(rows*cols) build.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve “product of array except self” with prefix sums?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use two passes: (1) Left prefix product: result[i] = product of all elements to the left of i. (2) Right suffix product: multiply result[i] by the product of all elements to the right of i (maintained as a running variable). This achieves O(n) time and O(1) extra space (not counting the output array). No division needed, handling zeros correctly.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide