Pattern 16: Prefix Sum

Deep Dive: Transform Then Query

Contiguous Array (Equal 0s and 1s)

nums = [0, 1, 0, 0, 1, 1, 0]. Transform: treat 0 as -1.

transformed = [-1, 1, -1, -1, 1, 1, -1]
prefix:        -1  0  -1  -2  -1  0  -1

Same prefix value at two indices -> subarray between them has sum 0
  -> equal 0s and 1s!

prefix[1]=0 and prefix[5]=0 -> subarray [2..5] has equal 0s/1s. Length=4.
prefix[0]=-1 and prefix[2]=-1 -> subarray [1..2]. Length=2.
prefix[0]=-1 and prefix[4]=-1 -> subarray [1..4]. Length=4.
prefix[0]=-1 and prefix[6]=-1 -> subarray [1..6]. Length=6. <- BEST

Answer: 6

Pattern: Transform the problem (0 -> -1), then use prefix sum + HashMap to find same-value pairs.

---

Signal: "Range sum", "subarray sum equals K", "contiguous array balance" Template: prefix_sum() in templates.py

When to Use

• "Range sum query" -> classic prefix sum
• "Number of subarrays with sum = K" -> prefix sum + HashMap
• "Balance / equal halves" -> transform + prefix sum
• "2D sub-rectangle sum" -> 2D prefix sum

Key Combo: Prefix Sum + HashMap

At each index: does (current_prefix - K) exist in the map?
If yes -> there's a subarray summing to K ending here.
Init map with {0: 1} to handle subarrays starting at index 0.

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Subarray Sum Equals K	Phase 1.2	15 min	[ ]
Contiguous Array	Phase 1.2	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Many range-sum queries on a static array" — precompute once, answer each query in O(1).
• "Number of subarrays whose sum equals K" (works even with negatives) — Prefix Sum + HashMap is the textbook solution.
• "Subarray with equal counts of X and Y" (0s and 1s, vowels and consonants) — encode as +1/−1 and look for repeated prefix values.
• "2D submatrix sum queries" — 2D prefix sum with inclusion–exclusion.
• "Subarray sum divisible by K" — bucket prefix sums by their remainder modulo K, then count pairs.

Anti-signals (looks like this pattern, isn't)

• "Longest contiguous subarray summing to ≤ K" with non-negative numbers — Sliding Window is simpler and more direct.
• "Mutable array with range queries" — Prefix Sum is broken by updates; use a Fenwick / Segment Tree.
• "Subarray sum equals K" with all-positive numbers, when only existence is asked — Sliding Window works in O(1) extra space.