Core Idea
Build a prefix array where prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. Then any range sum arr[l..r] = prefix[r+1] - prefix[l] in O(1). Build is O(n), queries are O(1).
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, v in enumerate(arr):
prefix[i+1] = prefix[i] + v
return prefix
# Range sum arr[l..r] (inclusive, 0-indexed)
def range_sum(prefix, l, r):
return prefix[r+1] - prefix[l]
Subarray Sum Equals K (LC 560)
Count subarrays whose sum equals k. Key insight: subarray_sum(i,j) = prefix[j] - prefix[i-1] = k iff prefix[i-1] = prefix[j] - k. Store prefix sum frequencies in a hashmap.
def subarray_sum(nums, k):
count = 0
curr = 0
freq = {0: 1} # empty prefix has sum 0
for n in nums:
curr += n
count += freq.get(curr - k, 0)
freq[curr] = freq.get(curr, 0) + 1
return count
Time O(n), Space O(n). The {0: 1} initialization handles the case where a prefix itself equals k.
Subarray Sum Divisible by K (LC 974)
Count subarrays whose sum is divisible by k. Two prefix sums with the same remainder mod k form a valid subarray. Use ((curr % k) + k) % k to handle negative remainders in Python.
def subarraysDivByK(nums, k):
count = 0
curr = 0
freq = {0: 1}
for n in nums:
curr = (curr + n) % k
rem = (curr % k + k) % k
count += freq.get(rem, 0)
freq[rem] = freq.get(rem, 0) + 1
return count
Continuous Subarray Sum (LC 523)
Check if any subarray of length ≥ 2 has a sum divisible by k. Store remainder → earliest index. If the same remainder appears at index j and previously at index i with j – i ≥ 2, the subarray nums[i+1..j] has sum divisible by k.
def checkSubarraySum(nums, k):
seen = {0: -1} # remainder -> first index
curr = 0
for i, n in enumerate(nums):
curr = (curr + n) % k
if curr in seen:
if i - seen[curr] >= 2:
return True
else:
seen[curr] = i
return False
2D Prefix Sum (LC 304)
For rectangle sum queries on a matrix, build a 2D prefix array. prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i-1,j-1).
# Build
for i in range(1, rows+1):
for j in range(1, cols+1):
prefix[i][j] = (matrix[i-1][j-1]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1])
# Query rectangle (r1,c1) to (r2,c2)
def query(r1, c1, r2, c2):
return (prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1])
Inclusion-exclusion: add top-left corner back to undo double-subtraction.
Difference Array (Range Update)
For problems with many range updates (add val to arr[l..r]) and a single final read, use a difference array: diff[l] += val; diff[r+1] -= val. Apply prefix sum once to reconstruct the final array. O(1) per update, O(n) to reconstruct.
# LC 1094 Car Pooling / LC 1109 Corporate Flight Bookings
diff = [0] * (n + 1)
for val, l, r in trips:
diff[l] += val
diff[r+1] -= val # r+1 because range is inclusive
result = list(itertools.accumulate(diff))
When to Reach for Prefix Sum
- “Subarray with sum equal to k” → prefix sum + hashmap
- “Range sum query, multiple queries” → 1D or 2D prefix array
- “Count subarrays with property” → prefix sum + frequency map
- “Range update then read all values” → difference array
- “Divisibility by k” → prefix sum mod k + frequency map
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the prefix sum technique and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A prefix sum array stores cumulative sums: prefix[i] = arr[0] + arr[1] + … + arr[i-1]. This allows any range sum arr[l..r] to be computed in O(1) as prefix[r+1] – prefix[l]. Build takes O(n). Use prefix sum when: you have multiple range sum queries on a static array, you need to count subarrays with a specific sum property, or you need to find subarrays divisible by k. The key insight for subarray sum problems: subarray_sum(i,j) = prefix[j+1] – prefix[i]. If you need subarray_sum = k, then prefix[j+1] – prefix[i] = k, which means prefix[i] = prefix[j+1] – k. This reduces the problem to a hashmap lookup.”}},{“@type”:”Question”,”name”:”How do you solve LC 560 (Subarray Sum Equals K)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a running prefix sum and a hashmap counting how many times each prefix sum has occurred. For each index j, you want to count how many previous indices i have prefix[i] = curr_sum – k. Initialize the hashmap with {0: 1} to handle subarrays that start at index 0. Python code: count=0; curr=0; freq={0:1}; for n in nums: curr+=n; count+=freq.get(curr-k,0); freq[curr]=freq.get(curr,0)+1. Time O(n), Space O(n). This handles negative numbers and zero-sum subarrays correctly, unlike the sliding window which only works for non-negative arrays. The {0:1} seed represents the empty prefix with sum 0.”}},{“@type”:”Question”,”name”:”How does the difference array technique work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A difference array enables O(1) range updates with O(n) final reconstruction. To add val to all elements in arr[l..r]: diff[l] += val; diff[r+1] -= val. After all updates, reconstruct with prefix sum: result[i] = diff[0] + diff[1] + … + diff[i]. This is the inverse of prefix sum. Use when: you have many range increment/decrement operations and only need the final array values (not intermediate states). LC examples: 1094 (Car Pooling), 1109 (Corporate Flight Bookings), 370 (Range Addition). Key constraint: does not support querying intermediate states efficiently — only the final state after all updates.”}},{“@type”:”Question”,”name”:”How do you build and query a 2D prefix sum?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Build: prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] – prefix[i-1][j-1]. This uses inclusion-exclusion: add the top and left cumulative sums, subtract the overlap (top-left rectangle counted twice). Query rectangle (r1,c1) to (r2,c2): prefix[r2+1][c2+1] – prefix[r1][c2+1] – prefix[r2+1][c1] + prefix[r1][c1]. Again inclusion-exclusion in reverse: subtract top and left strips, add back the corner (subtracted twice). Time: O(m*n) build, O(1) per query. LC 304 (Range Sum Query 2D). 2D prefix sum is also used in image processing (summed area table for fast box filter convutation).”}},{“@type”:”Question”,”name”:”What is the difference between prefix sum and sliding window for subarray problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sliding window works only when the array contains non-negative numbers and the target property is monotone (adding elements increases sum, removing decreases). Prefix sum + hashmap works for arrays with negative numbers and arbitrary sums. Use sliding window for: maximum subarray with at most K distinct elements, minimum window substring, subarray sum in non-negative array equals target. Use prefix sum for: subarray sum equals k with negative numbers (LC 560), count subarrays divisible by k (LC 974), number of subarrays with bounded maximum. The distinction: sliding window maintains a valid window by shrinking/growing; prefix sum finds pairs of indices whose difference equals the target.”}}]}
Meta coding interviews frequently test prefix sum and subarray patterns. See common questions for Meta interview: prefix sum and subarray problems.
Google coding interviews test prefix sum and range query patterns. Review problems for Google interview: prefix sum and range query problems.
Atlassian coding rounds include prefix sum and range problems. See patterns for Atlassian interview: prefix sum and array manipulation problems.