What is a Prefix Sum?
A prefix sum is the total of every value from the start of an array through a chosen position. It lets us calculate a range by subtracting two totals instead of adding the range again.
You need array indexes, running totals, and hash-map frequencies. The short version is: turn a subarray question into a question about the difference between two prefix totals.
The Core Idea: Look for an Earlier Total
Suppose the current running total is sum and we want a subarray ending here with total k.
What must the total have been immediately before that subarray began?
It must have been sum - k.
If that earlier total appeared three times, then three different subarrays ending here sum to k.
It is like reading an electricity meter. The energy used during one period is the later reading minus the earlier reading.
How One Prefix Finds a Subarray
The Rule You Keep True
Before the current prefix is stored, the map contains the frequency of every prefix ending before the current position. The answer counts every valid subarray ending at or before the current position.
Prefix information can be stored in several ways:
- Prefix array answers repeated fixed range-sum queries.
- Running prefix plus frequency map counts target-sum subarrays in one pass.
- Prefix products or suffix products combine ranges when subtraction is not the operation.
LC 560: With Negatives is the one that usually trips us up. A negative number can lower the running sum, so there is no safe rule for moving a sliding-window boundary. The prefix-difference equation still works without any change.
Picking the Right Shape
From Rule to Code
- Initialize the running prefix and store the empty prefix when needed.
- Add the current value to the running total.
- Compute the earlier prefix required by the current question.
- Use its stored count or value to update the answer.
- Store the current prefix for future positions.
The frequency-map version processes each item once, taking O(n) time and O(n) extra space.
When to use it
- •Many questions ask for sums over contiguous ranges.
- •A subarray condition can be rewritten using two prefix totals.
- •Negative values prevent a sliding window from moving predictably.
- •The prompt asks how many earlier positions create a target sum now.
How to identify it
- •The input is an array and the answer concerns contiguous subarrays or ranges.
- •The same elements would be added repeatedly by a direct solution.
- •A range sum from `l` to `r` can be expressed as `prefix[r] - prefix[l - 1]`.
- •The problem needs counts of earlier prefix values rather than only their existence.
Key insights
- →A prefix sum stores the total from the beginning through the current position.
- →A subarray ending now has sum `k` when an earlier prefix equals `currentSum - k`.
- →The empty prefix with sum zero must exist once before the scan starts.
- →A frequency map counts every earlier position that can begin a valid subarray.
- →Prefix sums work with negative values because they do not rely on monotonic movement.
Common mistakes
- 01Forgetting to initialize prefix sum zero with frequency one.
- 02Storing the current prefix before counting matches and accidentally including an empty current subarray.
- 03Using a set when duplicate prefix sums should contribute multiple subarrays.
- 04Confusing an element value with the running prefix total.
- 05Using a sliding window when negative values can make the sum rise or fall unpredictably.