patternDSA/Prefix Sum
Core Pattern → Pattern 30

Prefix Sum

Pre-compute cumulative sums so any range query is O(1). Pair with a hash map to count subarrays with a target sum in O(n) — works with negatives where sliding window fails.

Frequency:★★★★★
·~30 min·Easy–Medium·7 problems
The Core Shock

Every subarray sum by brute force is O(n²). One pass to build prefix sums turns any range query into O(1). Add a hash map to count/find subarrays in O(n) — even with negative numbers.

Brute force
O(n²) total
Two nested loops for every subarray. For n=10,000 that's 100 million operations just to answer 'count subarrays with sum k'.
Prefix sum + hash map
O(n) total
One build pass + one query pass. Each position does O(1) hash map work. Handles negative numbers — sliding window can't.
Core identity: sum(i..j) = prefix[j+1] - prefix[i]
So "does a subarray with sum k end at j?" ↔ "did we see prefix_sum − k before?"
Hash map stores frequencies of prefix sums seen → O(1) lookup per element

Two Modes of Prefix Sum

Mode 1: build the array for range queries. Mode 2: running sum + hash map for subarray search.

Mode 1: Prefix Array
When: Static range queries, 2D grids, 'sum of nums[l..r]' repeatedly
How: Build prefix[i+1]=prefix[i]+nums[i] once. Answer any range in O(1) with prefix[r+1]-prefix[l].
range_sum(l,r) = prefix[r+1] - prefix[l]
problems
Find Middle Index
Left/Right Sum Diff
Product of Array Except Self
2D matrix range sums
Mode 2: Running Sum + Map
When: Count/find subarrays with target sum, with negatives, divisibility
How: Maintain running sum + hash map of (prefix_sum → count). For each element: look up (sum-k), then record sum.
result += count[sum-k]; count[sum] += 1
problems
Subarray Sum = K
Max Size Subarray = K
Subarrays Divisible by K
Binary Subarrays with Sum

The 3-Step Framework

Sentinel → formula → hash map seed.

01
Build with the sentinel prefix[0] = 0

Always start with prefix[0]=0. This sentinel makes the formula prefix[r+1]-prefix[l] work even when l=0, without any if-else branch. For the hash map approach, seed count={0:1} — the empty prefix has sum 0 and has been 'seen once', enabling subarrays that start from index 0.

# Array mode:
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + nums[i]

# Hash map mode (seed first!):
count = defaultdict(int)
count[0] = 1   # empty prefix sentinel
prefix_sum = 0
Forgetting count[0]=1 is the #1 prefix sum bug. Without it, subarrays from index 0 to j (where prefix[j+1] == k exactly) are missed — because you'd look up count[k-k=0] and find 0 instead of 1.
02
Apply the core identity: sum(i..j) = prefix[j+1] - prefix[i]

For 'count subarrays with sum k': you need prefix[j+1] - prefix[i] == k, i.e., prefix[i] == prefix[j+1] - k. So look up count[prefix_sum - k] BEFORE recording the current prefix_sum. Order matters — looking up after recording would count single-element subarrays twice.

for num in nums:
    prefix_sum += num
    # 1. LOOKUP first
    result += count[prefix_sum - k]
    # 2. STORE after lookup
    count[prefix_sum] += 1
Lookup must happen BEFORE store. If you store first and then look up, you might count the empty subarray at the current position (sum=0) incorrectly. The order is: compute new prefix_sum → query count[sum-k] → record sum.
03
Apply variant: modulo for divisibility, first-index for max length

Divisible by K: use remainder as the map key — two equal remainders mean divisible difference. Max length subarray with sum k: store FIRST occurrence of each prefix sum (don't overwrite). The length is i - first[prefix_sum - k], and you want the earliest i to maximise length.

# Divisible by K:
remainder = prefix_sum % k
result += count[remainder]
count[remainder] += 1

# Max length subarray sum = k:
if prefix_sum not in first:
    first[prefix_sum] = i  # don't overwrite!
For max length: store FIRST occurrence. For count: use defaultdict and count ALL occurrences. These are different data structures for different questions. Mixing them up — e.g. overwriting first with the latest index — gives wrong max length answers.

Pattern Recognition

'subarray sum', 'range query', 'divisible', 'equal left and right' → prefix sum.

Use Prefix Sum When
Count subarrays with sum equal to k (any sign nums)
Find longest/shortest subarray with sum = k
Subarrays divisible by k (remainder trick)
Multiple range sum queries on static array
Find equilibrium / middle index (left sum = right sum)
2D matrix range queries (2D prefix sum)
Binary arrays: count subarrays with sum = goal
Sum of absolute differences in sorted array
Common Pitfalls
Forgetting count[0]=1 (missing subarrays from index 0)
Storing before looking up — double-counts zero-sum subarrays
Using prefix[r]-prefix[l-1] instead of prefix[r+1]-prefix[l]
Max length: overwriting first-seen index (must store only first)
Negative remainder in Java/C++: use ((x%k)+k)%k
Using sliding window when array has negative numbers
Off-by-one: prefix has n+1 elements, nums has n elements
Divisible by K: seeding count={0:1} still needed for full-array sums