LeetCode Solutions← Back to Patterns
Arrays & Sliding WindowEasy
Prefix Sum
Precompute cumulative sums to answer range queries in O(1).
How it works
Prefix Sum builds an auxiliary array where prefix[i] = sum of the original array from index 0 to i-1. Once built in O(n), any range sum query [i, j] can be answered in O(1) as prefix[j+1] - prefix[i]. This is especially powerful when you have many queries on the same static array. A common extension combines Prefix Sum with a Hash Map to find subarrays with a target sum: as you build the prefix sum, check if (currentSum - target) has been seen before — if yes, the subarray between those two positions has exactly the target sum.
Interactive Playground
Given array [3, 1, 4, 1, 5]. Build prefix sum array.
Speed
When to use
- Range sum queries on a static array
- Subarray sum equals k
- Counting subarrays with specific properties
✅Tips
1Use a 1-indexed prefix array (size n+1) to avoid off-by-one errors: prefix[0] = 0.
2For "subarray sum equals k", combine prefix sum with a HashMap: store {prefixSum: count} as you iterate.
3Prefix Sum can be extended to 2D grids — prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i,j).
4Works for any associative operation, not just sum — prefix XOR, prefix product (with care for zeros).
❌Common Mistakes
!Off-by-one: range sum [l, r] inclusive = prefix[r+1] - prefix[l], not prefix[r] - prefix[l].
!Forgetting to initialize the HashMap with {0: 1} for the "subarray sum equals k" variant — misses subarrays starting from index 0.
!Using prefix sum on a mutable array — it must be rebuilt after each update (use a Fenwick Tree instead).
!Overflow when the array values are large integers — use long/BigInt as appropriate.
💡 Key Insight:sum[i..j] = prefix[j+1] - prefix[i]. Build once, query many times.