All patterns
Prefix Sum
Precompute running totals so any range sum is a subtraction.
time O(n)space O(n)
What it is
Let P[i] be the sum of the first i elements. Then sum(l..r) = P[r+1] − P[l]. Combined with a HashMap of earlier prefixes it solves range-sum-equals-k problems even with negative numbers.
When to reach for it
- Many range sum queries
- Subarray with sum k, divisible by k, or balanced counts
- 2D region sums
Clues in the problem
- Inner loop re-adds a range each time
- Negative numbers rule out sliding window
Template
def count_subarrays(a, k):seen = {0: 1} # prefix -> how many timespref = ans = 0for x in a:pref += xans += seen.get(pref - k, 0)seen[pref] = seen.get(pref, 0) + 1return ans
Practice problems
- Subarray Sum Equals K
- Range Sum Query
- Contiguous Array
- Product of Array Except Self
Common mistakes
- Forgetting the empty prefix {0: 1}
- Integer overflow in prefix totals
- Off-by-one between P[r+1] and P[r]