← All patterns
Prefix Sum / Difference Array
Precompute cumulative sums (prefix[i] = sum of elements 0..i) to answer range-sum queries in O(1), or use a difference array for range updates.
When to use it
- Subarray sum queries, subarray sum equals K (prefix sum + hash map).
- Product of array except self (prefix + suffix products).
- Range update problems (difference array).
Signals in the problem statement
- 'Subarray sum', 'range query', 'continuous subarray'.
- Brute force recomputes the same prefix work repeatedly.
Common pitfalls
- Off-by-one in indices: prefix[i] usually includes element i, so range [L, R] sum is prefix[R] - prefix[L-1] (or handle 0-index carefully).
- Forgetting to handle prefix[0] as 0 or a sentinel when using a hash map for subarray-sum-equals-K.
Practice Problems
Subarray Sum Equals K
MediumAsked at: Amazon, Meta, Google
Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals k.
Time: O(n) · Space: O(n)
Product of Array Except Self
MediumAsked at: Amazon, Meta, Apple, Microsoft
Given an array nums, return an array where output[i] is the product of all elements except nums[i]. Do it in O(n) without division.
Time: O(n) · Space: O(1) ignoring output array