Prefix Sum
- Build a prefix array and answer arbitrary range-sum queries in O(1)
- Pair prefix sums with a hash map to count subarrays matching a target sum, even with negative values
- Apply difference arrays for batch range updates at O(1) per update, then recover the final array in a single cumulative pass
The prefix sum pattern transforms O(n) range sum queries into O(1) operations by precomputing cumulative sums. Combined with hash maps, it handles subarray counting problems, including those with negative numbers, that sliding window cannot solve.
What Is the Prefix Sum Pattern?
Brute force computes a subarray sum by walking every element in the range. For a single query that's O(n). For q queries on an array of n elements, the total work is O(n × q). Prefix sum collapses each query to a single subtraction.
Precompute a running total. Given nums = [2, 4, 1, 3, 5], the prefix array stores cumulative sums: prefix = [0, 2, 6, 7, 10, 15]. The sum of elements 1 through 4 is prefix[5] - prefix[1] = 15 - 2 = 13. One arithmetic operation instead of iterating through four elements.
In general: sum(nums[l..r]) = prefix[r+1] - prefix[l]. O(n) to build, O(1) per query.
The leading zero matters. prefix[0] = 0 makes the formula work uniformly for every range, including those starting at index 0. Without it, those ranges need special handling. Allocate an array of length n+1 and set the first slot to zero.
Watch how the prefix array is built step by step:
Building the Prefix Array
Step 1 of 6 · Sentinel prefix[0] = 0 lets every range query use the same formula. No special case for ranges starting at index 0.
prefix[j] - prefix[i] gives the sum of elements i through j-1. Precompute all running totals once in O(n), then answer any range query in O(1). When you see "subarray sum," think prefix subtraction. Declare your indexing convention upfront (e.g., 1-indexed prefix array of length n+1) to prevent off-by-one confusion during implementation.
The Core Formula
The formula sum(nums[l..r]) = prefix[r+1] - prefix[l] enables three major applications:
Range queries: The formula is applied directly: prefix[r+1] - prefix[l] gives the sum of elements l through r. No iteration needed.
Subarray sum = k: Rearrange prefix[j] - prefix[i] = k to prefix[i] = prefix[j] - k. At each position j, the algorithm checks whether prefix[j] - k has appeared before. This converts an O(n²) nested loop (checking every start-end pair) into an O(n) hash map lookup: for each endpoint, ask "does a matching start point exist?"
Divisibility by k: Two prefix sums with the same remainder mod k produce a subarray sum that is a multiple of k. The hash map tracks remainders instead of raw prefix values.
The Complexity Transformation
| Operation | Brute Force | With Prefix Sum |
|---|---|---|
| Preprocess | None | O(n) once |
| Single range query | O(n) | O(1) |
| m queries | O(m x n) | O(n + m) |
Range Sum Queries
With the 1-indexed convention, the range sum formula is clean and requires no special cases. The derivation follows step by step:
Range Sum Query
Query: sum of nums[1..3]. We want 4 + 1 + 3 = 8
How to Recognize Prefix Sum Problems
Certain phrases in problem statements signal prefix sum applicability.
Common Problem Structures
"Subarray sum equals k" or "contiguous elements with sum" problems reduce to searching for a previous prefix sum with a specific value. At each position j, the algorithm asks: "has any earlier prefix sum equaled current_sum - k?" That question is a single hash map lookup, turning an O(n) scan of all earlier positions into an O(1) operation. The algebra (prefix[j] - prefix[i] = k rearranged to prefix[i] = prefix[j] - k) explains why it works, but the core move is the lookup.
"Range sum query" or "multiple queries" problems benefit from O(n) preprocessing followed by O(1) per query. Without preprocessing, m queries on n elements costs O(m x n).
"Count subarrays with property X" problems transform O(n²) iteration into O(n) hash map lookups. Instead of checking every possible subarray, the algorithm tracks prefix values and counts matches.
"Array may contain negative numbers" signals that sliding window won't work. Sliding window assumes shrinking the window decreases the sum; negatives violate this because removing a negative element increases the sum.
When Sliding Window Fits vs When It Doesn't
Sliding window relies on monotonicity: expanding the window increases the sum, and shrinking decreases it. This assumption enables greedy pointer movement. But when the array contains negative numbers, removing an element from the left can increase the sum (if that element was negative), breaking the greedy logic. The window might skip over valid solutions.
Prefix sum sidesteps this entirely by using pure algebra. The formula sum(l, r) = prefix[r+1] - prefix[l] works regardless of element signs. Instead of greedy pointer decisions, the algorithm looks up complements in a hash map.
Negative numbers rule out sliding window for sum-based subarray problems. Shrinking the window can increase the sum when negative elements leave, which breaks the greedy movement rule.
- • Array has negative numbers: use prefix sum. The formula works regardless of sign.
- • "At most k" with non-negative values: sliding window is simpler and uses O(1) space.
- • "Exactly k" or "count all subarrays": prefix sum with a hash map.
- • Multiple range queries on a static array: build a prefix array once, then answer each query in O(1).
Which Template Should I Use?
Match the signal in the problem statement to the right technique:
| Signal in the Problem | Technique to Use |
|---|---|
| Range sum queries on a static array | Prefix Sum Array (Template 1) |
| Count subarrays with sum = k (negatives possible) | Prefix Sum + Hash Map (Template 2) |
| Divisibility by k | Prefix Sum + Mod Map (Template 3) |
| "At most k" constraint, all positives | Sliding Window instead |
| Multiple range updates, then query | Difference Array |
The Three Prefix Sum Templates
Three templates cover most prefix sum problems. The choice depends on what the problem requires:
| Need | Template | Data Structure |
|---|---|---|
| Single query, fixed range? | Template 1: Direct subtraction | Prefix array only |
| Count subarrays with sum = k? (negatives possible) | Template 2: Hash map | Prefix array + hash map |
| Count subarrays divisible by k? | Template 3: Modulo + hash map | Hash map with remainders |
Template 1: Basic Range Sum Query
Use this template for answering multiple range sum queries on a static array. Build the prefix array once, then answer each query in O(1).
Complexity: O(n) preprocessing, O(1) per query, O(n) space.
Template 2: Subarray Sum Equals K
This template handles negative numbers.
The Derivation
Start from the core formula: every subarray sum is prefix[j] - prefix[i]. Finding subarrays with sum = k means finding pairs (i, j) where prefix[j] - prefix[i] = k.
So at each position j, instead of iterating through all earlier positions, the algorithm looks up how many times the value prefix[j] - k has appeared. By storing all prefix sums in a hash map, each lookup becomes O(1) instead of O(n).
Implementation
See the complete animated walkthrough of this algorithm in the Complete Walkthrough section below.
Why a Hash Map Instead of an Array?
Template 1 uses an array because indices go 0 to n. Template 2 uses a hash map because prefix sums can be any value (positive, negative, huge). A hash map stores only the sums that actually appear.
Why {0: 1}? The Base Case
The {0: 1} initialization is required, not a trick:
When does current_sum - k = 0? When current_sum = k. This means the subarray from index 0 to the current position has sum exactly k. The required "earlier prefix" is prefix[0] = 0, which represents "the sum before any elements" or "taking zero elements."
The {0: 1} says: "There is exactly one way to have a prefix sum of 0, which is taking zero elements from the start." This is the base case: the sum before any elements.
{0: 1} silently misses every subarray that starts at index 0. If current_sum == k, the complement is 0, which must already be in the map. Without it, the lookup returns 0 and those valid subarrays are never counted. No error, no warning, just wrong answers.Template 3: Count Subarrays Divisible by K
Use this template when counting subarrays where the sum is divisible by k.
If prefix[j] % k == prefix[i] % k, then the difference prefix[j] - prefix[i] is divisible by k. Algebraically:
A concrete example: if prefix[3] = 14 and prefix[1] = 4 with k = 5, then 14 % 5 = 4 and 4 % 5 = 4. Same remainder. The subarray sum is 14 - 4 = 10, which is divisible by 5. The equal remainders guarantee the difference is a multiple of k.
So two prefixes with the same remainder mod k produce a subarray sum divisible by k. Track remainder counts instead of full prefix sums:
% always returns a non-negative result when the divisor is positive, so -1 % 3 = 2 in Python. Java and C++ return a negative remainder instead: -1 % 3 = -1. Negative remainders don't match positive ones in a hash map, so the lookup silently fails. In Java or C++, normalize with ((x % k) + k) % k to guarantee a non-negative result.The Difference Array
The difference array is the inverse of prefix sum: instead of fast queries on a static array, it enables fast range updates. Instead of iterating through every element in the range, you make just two point modifications.
Difference Array: Inverse of Prefix Sum
To add val to every element from index l to r (inclusive), instead of updating each element individually (O(n) per update), use two O(1) operations:
Difference Array
Start with an array of 6 zeros. We want to apply range updates efficiently.
The reconstruction step is exactly a prefix sum. The difference array records "changes" at boundaries, and prefix sum accumulates them into final values. This is why they are inverses: prefix_sum(difference_array(arr)) = arr.
Prefix sum converts point values into cumulative sums. Difference array converts range updates into point changes. Applying prefix sum to a difference array reconstructs the original. They undo each other, like addition and subtraction.
Complete Walkthrough: Subarray Sum = K
Subarray Sum Equals K combines every prefix sum concept: the complement lookup, the {0: 1} base case, and the check-before-store ordering.
Problem Statement
Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k. The array may contain negative numbers.
Step 1: Acknowledge the Brute Force
The brute force fixes a start index, then extends the end index while maintaining a running sum. That is O(n²) pairs, each answered in O(1), giving O(n²) total. The goal is to identify what structure the prefix sums share that lets us avoid examining every pair.
Step 2: Recognize the Pattern
Every subarray sum is the difference of two prefix values: prefix[j] - prefix[i] = k. Rearranged: prefix[i] = prefix[j] - k. At each position j, the question becomes: how many earlier positions i have a prefix sum equal to prefix[j] - k? A hash map answers that in O(1) per position, reducing total work to O(n).
Step 3: Code the Optimal Solution
The implementation follows directly from Template 2. Initialize the map with {0: 1} to cover subarrays starting at index 0, check the complement before storing each new prefix, and return the count.
Step 4: Watch the Algorithm in Action
This diagram traces every step with nums = [1, 2, 3, -2, 5] and k = 3:
Subarray Sum = K (Hash Map Lookup)
Initialize hash map with {0: 1}. One way to have prefix sum 0 (taking zero elements)
Common Bugs in This Problem
Bug: Missing the base case
Bug: Store before check
Edge Cases to Mention
- Empty array: Return 0. No elements means no subarrays.
- All zeros, k = 0: Every subarray sums to 0. For n elements: n*(n+1)/2 subarrays.
- Single element: Check if nums[0] == k. The {0: 1} base case handles this.
- k = 0: Still works. The complement is
current_sum - 0 = current_sum. Counts how many earlier prefix sums equal the current one. - Negative k: Works because the formula is algebraic, not dependent on sign.
- Acknowledge brute force O(n²) and why it's slow
- Recognize: "subarray sum = difference of prefix sums"
- Derive: rearrange to complement lookup
- State the base case and why it's needed
- Code the solution with check-before-store order
- Analyze complexity and edge cases
Common Pitfalls
Forgetting the Base Case
When current_sum == k, the complement is 0. Without {0: 1} in the hash map, the lookup returns 0 and every valid subarray starting at index 0 is silently missed. No error is thrown. The code runs cleanly and returns the wrong answer.
Off-by-One in Range Queries
Confusing indexing conventions causes subtle bugs. The 1-indexed convention (prefix array of length n+1 where prefix[0] = 0) avoids special cases. With this convention, sum(nums[l..r]) = prefix[r+1] - prefix[l]. The 0-indexed convention requires a branch when l = 0.
long instead of int. In C++, use long long. Python handles arbitrary precision natively, so this only affects typed languages.Processing Order in Hash Map Lookups
In the subarray sum template, the complement must be checked before storing the current prefix. Storing first makes the current position count as a valid "earlier" prefix, which is wrong. The algorithm needs prefixes that came before the current position, not including it.
Prefix Sum vs Sliding Window
Both handle subarray problems, but they apply under different conditions. The simplest decision rule: if the array can contain negative numbers, sliding window won't work for sum-based problems, so use prefix sum. If all values are non-negative, try sliding window first because the code is simpler and uses less space.
| Aspect | Prefix Sum | Sliding Window |
|---|---|---|
| Works with negatives | Yes | No |
| "Exactly k" problems | Natural fit | Needs atMost trick |
| "At most k" problems | Harder | Natural fit |
| Multiple range queries | O(1) each | N/A |
| Space | O(n) or O(unique values) | O(1) to O(k) |
Limitation: Prefix sums work for sums but not for min/max queries, because you cannot "undo" a min with subtraction the way you can undo addition. For range min/max, use a sparse table or segment tree instead.
Sliding window is a greedy algorithm that depends on monotonicity (expanding the window always increases the sum, shrinking always decreases it). Prefix sum is an algebraic technique that works because subtraction undoes addition. When negatives are present, monotonicity breaks and the greedy pointer decisions fail. When all values are non-negative, sliding window is simpler because it avoids the O(n) preprocessing and hash map overhead.
A concrete example demonstrates the failure. For nums = [-1, 1, -1, 1] and target sum = 0, a sliding window starting at index 0 with sum -1+1 = 0 finds one valid subarray. But shrinking the window by removing -1 from the left increases the sum to 1, causing the window to skip past other valid subarrays. The window cannot "unsee" the effect of removing negative elements.
Practice Problems
Practice these in order. Start with range queries, then move to hash map variants.
Basic Range Queries
| Problem | Difficulty | Approach |
|---|---|---|
| Range Sum Query (Immutable) | Easy | Direct application of Template 1. Build a prefix array once in the constructor, then answer each query in O(1) via subtraction. The simplest prefix sum problem and the right starting point. |
Subarray Sum = K Variants
| Problem | Difficulty | Approach |
|---|---|---|
| Subarray Sum Equals K | Medium | The canonical prefix sum + hash map problem. The algebraic rearrangement prefix[i] = prefix[j] - k transforms O(n²) brute force into O(n) hash map lookups. The {0: 1} initialization is mandatory for subarrays starting at index 0. |
| Continuous Subarray Sum | Medium | Divisibility variant with a length >= 2 constraint. Track the first index where each remainder appears. A match is valid only if the current index minus the stored index is at least 2. |
| Subarray Sums Divisible by K | Medium | Pure divisibility counting via Template 3. Two prefixes with the same remainder mod k produce a divisible subarray sum. Handle negative remainders by adding k when the remainder is negative. |
Count Subarrays
| Problem | Difficulty | Approach |
|---|---|---|
| Number of Subarrays with Bounded Maximum | Medium | Reframe as prefix sum of "valid" count at each position. At each index, track how many subarrays ending here have max within bounds. |
| Count Number of Nice Subarrays | Medium | Replace each element with 1 (odd) or 0 (even), then apply "subarray sum = k" via Template 2. Alternatively use the atMost(k) - atMost(k-1) decomposition. |
Prefix/Suffix Product & Difference Array
| Problem | Difficulty | Approach |
|---|---|---|
| Product of Array Except Self | Medium | Prefix and suffix products instead of sums. Build prefix_product from left and suffix_product from right, then multiply them. Avoids division, which would fail on zeros. |
| Corporate Flight Bookings | Medium | Each booking is a range update [first, last] += seats. Apply all bookings to the difference array, then reconstruct via prefix sum. |
| Shifting Letters II | Medium | Difference array on character shifts. Each operation shifts a range of letters forward or backward. Accumulate shifts via difference array, then apply the net shift to each character. |
Reference Templates
Compact code shapes for quick recovery. Each template includes the context that determines when to use it.
Use when answering multiple range sum queries on a static array.
Use when counting subarrays whose sum equals k. Works with negative numbers.
Use when counting subarrays whose sum is divisible by k.
Use when applying many range updates before reading final values. Each update is O(1); reconstruction is one O(n) pass.
Pattern Recap
Range queries use O(n) preprocessing followed by O(1) per query via prefix[r+1] - prefix[l]. The leading zero at prefix[0] makes the formula work for every range without special-casing index 0.
Exact sum counting rearranges prefix[j] - prefix[i] = k to prefix[i] = prefix[j] - k, turning an O(n²) search into O(n) hash map lookups. The {0: 1} entry counts the empty prefix, covering subarrays that start at index 0. The check must happen before the store so the current position cannot match itself.
Negative numbers do not break prefix sums. The formula is pure arithmetic: subtraction undoes addition regardless of element sign. Sliding window fails with negatives because its greedy pointer decisions require monotonic sum behavior. Prefix sum avoids that assumption entirely by using a hash map lookup instead.
Difference arrays are the inverse operation. Where prefix sum converts point values into cumulative sums, a difference array converts a range update into two point changes. Applying a prefix sum to the difference array reconstructs the final values. This is useful only when all updates complete before any queries are answered.
Rebuilding the Pattern
When a prefix sum problem feels unclear, start with the question: can the property being asked about be expressed as the difference of two prefix values? For range sum queries the answer is direct. For counting problems, the rearrangement step is the core move.
For counting subarrays, rewrite the target condition as an equation involving two prefix values, then isolate the earlier prefix on one side. The question becomes: how many earlier prefix values satisfy that equation? A hash map answers it in O(1) because the map accumulates every prefix as the scan advances. The {0: 1} base case and check-before-store order both follow from the same constraint: the map must only contain prefixes that came strictly before the current position.
For divisibility, the rearrangement produces a modular condition instead of an exact match. Two prefix sums with the same remainder mod k differ by a multiple of k, so the map stores remainders rather than raw sums. The structure of the loop is identical to Template 2; only what gets stored in the map changes.
For range updates, ask whether all updates can complete before any values are read. If yes, encode each update as two point changes in the difference array and run one prefix sum pass to reconstruct. If updates and queries are interleaved, a segment tree is required instead. The difference array is the right choice when batch processing is possible.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Ready to test it?
10 questions covering prefix sum patterns and difference arrays.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Prefix Sum in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.