# Prefix Sums — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/h-prefix

> Range sums in constant time.

## sum(i..j) = prefix[j] - prefix[i]

A **prefix sum** array stores running totals, so any subarray sum is a difference of two prefixes. Combined with a hash map counting earlier prefixes, "how many subarrays sum to k" becomes one pass: at each position, count earlier prefixes equal to `prefix - k`. Unlike a sliding window, this works with **negative numbers**. Two-dimensional prefix sums answer rectangle-sum queries in grids.

## Counting subarrays that sum to k, run

I ran this with Python 3.12.3 (standard library only). Three test cases, including one with negative numbers where a sliding window would fail; the empty prefix (0 seen once) counts subarrays starting at index 0.

```python
# Count subarrays summing to k with prefix sums + a hash map: O(n)
from collections import defaultdict

def subarray_sum(nums, k):
    count, prefix = 0, 0
    seen = defaultdict(int)
    seen[0] = 1                          # empty prefix
    for x in nums:
        prefix += x
        count += seen[prefix - k]        # earlier prefixes that make a sum of k
        seen[prefix] += 1
    return count

print(subarray_sum([1, 1, 1], 2))            # [1,1] twice
print(subarray_sum([1, 2, 3], 3))            # [1,2] and [3]
print(subarray_sum([3, -1, 1, 2, -2, 3], 3)) # negatives are fine
```

Output:

```
2
2
7
```

## Seed the map with prefix 0

Forgetting seen[0] = 1 misses subarrays that start at the beginning.

**Quiz:** Why use prefix sums instead of a sliding window for "subarray sum equals k"?

- [ ] They use no memory
- [x] They work even when the array contains negative numbers
- [ ] They sort the array
- [ ] They are always O(1) overall

*Answer:* They work even when the array contains negative numbers. Windows need monotonic sums.