Prefix sum on LeetCode is one equation wearing nine costumes. Once you write down that the sum of a slice equals one running total minus another, every problem below turns into a question about what to store and what to look up. Nine of them are here: 1480, 303, 304, 560, 974, 325, 1524, 525, and 523.
All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series.
The nine problems at a glance
| # | Problem | Difficulty | Family |
|---|---|---|---|
| 1480 | Running Sum of 1d Array | Easy | Build the table |
| 303 | Range Sum Query — Immutable | Easy | Build the table |
| 304 | Range Sum Query 2D — Immutable | Medium | Build the table |
| 560 | Subarray Sum Equals K | Medium | Stream into a map |
| 974 | Subarray Sums Divisible by K | Medium | Stream into a map |
| 1524 | Number of Sub-arrays With Odd Sum | Medium | Stream into a map |
| 325 | Maximum Size Subarray Sum Equals k | Medium (Premium) | Stream into a map |
| 525 | Contiguous Array | Medium | Stream into a map |
| 523 | Continuous Subarray Sum | Medium | Stream into a map |
Note that 325 sits behind LeetCode Premium, so you can read the approach here but you won’t be able to submit against it without a subscription.
The one equation
Let P[i] be the sum of the first i elements, so P[0] = 0. Then the sum of the slice from i to j is:
sum(i…j) = P[j+1] − P[i]
Read left to right, that says: precompute every P once, then answer any range query with a single subtraction. That’s the first family — problems 1480, 303 and 304.
Now rearrange it. If you want the slice to sum to some target k, then P[j+1] − P[i] = k, which means:
P[i] = P[j+1] − k
Read that way, the equation stops being about arithmetic and becomes a lookup. Walk the array keeping a running total, and at each position ask a single question: have I seen the value “running minus k” before? Every hit is a slice ending here that sums to k. That’s the second family, and it’s six of the nine problems.
The reason this collapses an O(n²) enumeration into one pass is that you never look for the slices. You look for their left edges, and a hash map hands you all of them at once.
Family one: build the table, then subtract
1480. Running Sum of 1d Array (Easy)
The task: return an array where each position holds the sum of everything up to and including that position.
This is the pattern with nothing built on top of it. It exists so you can check that you can write the recurrence without thinking.
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
int n = (int)nums.size();
vector<int> result(n);
result[0] = nums[0];
for (int i = 1; i < n; ++i) {
result[i] = result[i - 1] + nums[i];
}
return result;
}
};One style note that matters more than it looks. If you allocate the result zero-filled, it’s tempting to write result[i] += nums[i] + result[i-1], which works because the slot starts at zero. Don’t. += tells a reader that something is accumulating across iterations, and nothing is; each slot is written exactly once. Use = and let the code say what it does.
303. Range Sum Query — Immutable (Easy)
The task: build a structure over a fixed array that answers “what’s the sum between these two indices, inclusive?” repeatedly. The array never changes.
The naive version re-adds the range on every call. With many queries that’s O(n) each. Build the running sums once in the constructor and every query is one subtraction.
The interesting decision here is the padding. If your table is the same length as the input, then sumRange(left, right) is P[right] − P[left-1], and left == 0 needs a special case because there is no P[-1]. Make the table one slot longer with a leading zero instead, and the special case evaporates:
class NumArray {
// prefix[i] = sum of the first i elements, so prefix[0] = 0
vector<int> prefix;
public:
NumArray(vector<int>& nums) : prefix(nums.size() + 1, 0) {
for (int i = 0; i < (int)nums.size(); ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left]; // no branch for left == 0
}
};Padding costs one integer and removes a branch that is easy to get wrong. It also happens to be the trick that makes the 2-D version readable, which is the next problem.
304. Range Sum Query 2D — Immutable (Medium)
The task: the same thing on a grid. Answer “what’s the sum of this rectangle?” in constant time per query.
Define prefix[i][j] as the sum of the whole rectangle above and to the left of cell (i, j). Building it isn’t “previous plus current” any more, and the reason is worth stating precisely: the strip above and the strip to the left overlap. Everything in the top-left corner region belongs to both, so adding them counts that corner twice and you have to put one copy back.
prefix[i][j] = cell + above + left − corner
That’s inclusion-exclusion, and reading a query out of the finished table is the same idea run backwards. To carve out one rectangle you take everything up to its bottom-right corner, subtract the band above it and the band to its left, and then add back the top-left corner region that you just removed twice.
class NumMatrix {
// prefix[i][j] = sum of the rectangle above and left of (i, j).
// Padded with a zero row and a zero column, so no edge cases below.
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix)
: prefix(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0)) {
int rows = (int)matrix.size();
int cols = (int)matrix[0].size();
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
prefix[i][j] = matrix[i - 1][j - 1]
+ prefix[i - 1][j] // the strip above
+ prefix[i][j - 1] // the strip to the left
- prefix[i - 1][j - 1]; // their shared corner, counted twice
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
// matrix cell (r, c) lives at prefix[r + 1][c + 1]
return prefix[row2 + 1][col2 + 1]
- prefix[row1][col2 + 1]
- prefix[row2 + 1][col1]
+ prefix[row1][col1];
}
};Without the padding row and column, both loops need special handling for the top row and the leftmost column, because prefix[i-1][j-1] doesn’t exist there. With it, there is not a single conditional in the class.
One thing to check before shipping a prefix table anywhere: the largest total it can hold. That’s rows × columns × the biggest absolute value. These constraints keep it inside a 32-bit int, but the moment that product passes about 2.1 × 109 the table has to be long long, and the failure is a silent wrong answer rather than a crash.
Family two: stream the running sum into a map
The remaining six problems never build a table. They keep one running total and one map, and they all have this shape:
map seen;
seen[starting key] = base value; // the empty prefix, before any element
running = 0;
for (each element) {
running += element;
key = transform(running); // the sum itself, or the sum mod something
if (seen contains the key you want) update the answer;
record the current key in seen; // AFTER the lookup, never before
}Two decisions turn that skeleton into a specific problem. What you hash is either the running sum itself, which answers “sums to exactly k”, or the running sum modulo something, which answers “is divisible by k”. What you store is either how many times you’ve seen a key, which answers counting questions, or the earliest index at which you saw it, which answers longest-and-does-it-exist questions.
That’s a two-by-two, and the six problems fill it in:
| # | Hashes | Stores | Looks up | Answer |
|---|---|---|---|---|
| 560 | running sum | frequency | running − k | count of slices |
| 974 | running sum mod k | frequency | the same residue | count of slices |
| 1524 | running sum mod 2 | frequency | the opposite parity | count of slices |
| 325 | running sum | earliest index | running − k | longest slice |
| 525 | balance (0 counts as −1) | earliest index | the same balance | longest slice |
| 523 | running sum mod k | earliest index | the same residue | does one exist |
The “same key, not key − k” rows are worth pausing on. If two running totals leave the same remainder when divided by k, their difference is a multiple of k. So for divisibility you don’t subtract anything, you just look for a repeat. That single sentence is the whole of 974, 523 and 1524.
560. Subarray Sum Equals K (Medium)
The task: count how many contiguous slices sum to exactly k. Values can be negative.
This is the equation rearranged, with a frequency map because several earlier prefixes can share a value.
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> freq; // prefix sum -> how many times it has occurred
freq[0] = 1; // the empty prefix, so slices starting at 0 count
int running = 0;
int answer = 0;
for (int num : nums) {
running += num;
auto it = freq.find(running - k);
if (it != freq.end()) answer += it->second;
++freq[running]; // after the lookup, or you match yourself
}
return answer;
}
};Both marked lines are load-bearing. Drop freq[0] = 1 and every slice that starts at index 0 goes uncounted. Move ++freq[running] above the lookup and the current prefix can match itself: on the input [1] with k = 0 that returns 1 instead of 0, because it counts the empty slice as a real one.
Notice what makes the hash map necessary rather than merely convenient. If every value were positive, the running sum would only increase, and a sliding window with two pointers would solve this in O(1) space. Negatives break monotonicity, the window can’t know when to shrink, and hashing the prefixes is what replaces it. Interviewers ask about this on purpose.
A trace of 560, since the rest inherit it
Take nums = [2, −1, 3, 1, −3] with k = 3.
| Step | Element | Running | Wants | Found | Answer | Map after |
|---|---|---|---|---|---|---|
| 0 | — | 0 | — | — | 0 | {0:1} |
| 1 | 2 | 2 | −1 | no | 0 | {0:1, 2:1} |
| 2 | −1 | 1 | −2 | no | 0 | {0:1, 2:1, 1:1} |
| 3 | 3 | 4 | 1 | once | 1 | {…, 4:1} |
| 4 | 1 | 5 | 2 | once | 2 | {…, 5:1} |
| 5 | −3 | 2 | −1 | no | 2 | {…, 2:2} |
The hit at step 3 found running total 1, which was recorded at step 2, so the slice runs from step 3 to step 3: the single element [3]. The hit at step 4 found running total 2, recorded at step 1, so the slice is [−1, 3, 1]. Both sum to 3, and the map produced them without any inner loop.
974. Subarray Sums Divisible by K (Medium)
The task: count the contiguous slices whose sum is divisible by k.
Same shape as 560, but hash the residue and look for a repeat rather than for running − k. There’s a bonus: since there are only k possible residues, the map can be a plain vector, which drops the hashing entirely.
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
vector<int> freq(k, 0); // only k residues exist, so a vector beats a hash map
freq[0] = 1;
int running = 0;
int answer = 0;
for (int num : nums) {
running = (running + num) % k;
if (running < 0) running += k; // C++ % takes the sign of the dividend
answer += freq[running]; // every earlier prefix with this residue
++freq[running];
}
return answer;
}
};The negative-residue line is not defensive programming, it is the difference between working code and a crash. In C++, -1 % 2 is -1, not 1. Delete that line and freq[running] indexes a vector at −1: compiled with the address sanitizer, the input [−1, 2, 9] with k = 2 reports a heap-buffer-overflow on the read. On the judge it’s a silent out-of-bounds access that may or may not produce a wrong answer depending on what happens to be in memory.
1524. Number of Sub-arrays With Odd Sum (Medium)
The task: count the contiguous slices whose sum is odd, modulo 109 + 7.
This is 974 with k = 2, so the “map” is two counters. The twist is that odd is a difference in parity rather than a match: a slice is odd exactly when its two endpoints have opposite parities. So you look up the other bucket instead of your own.
class Solution {
public:
int numOfSubarrays(vector<int>& arr) {
const int MOD = 1000000007;
long long freq[2] = {1, 0}; // the empty prefix sums to 0, which is even
int parity = 0;
long long answer = 0;
for (int num : arr) {
parity ^= (num & 1); // only the parity of the running sum matters
answer = (answer + freq[parity ^ 1]) % MOD; // the opposite bucket
++freq[parity];
}
return (int)answer;
}
};Tracking the parity bit with XOR instead of computing running % 2 is not just tidier. It sidesteps the exact negative-remainder trap that 974 needed a guard for, because num & 1 is 1 for odd numbers whether they’re positive or negative. This problem’s constraints happen to rule out negatives anyway, but writing it this way means you aren’t quietly depending on that.
325. Maximum Size Subarray Sum Equals k (Medium, Premium)
The task: instead of counting the slices that sum to k, return the length of the longest one, or zero if there isn’t one.
Counting becomes maximizing, so the map’s value changes from a tally to an index. And because you want the longest slice, you want the earliest left edge, which means each key must be written once and never overwritten.
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
// prefix sum -> the earliest index that produced it
unordered_map<long long, int> firstIndex;
firstIndex[0] = -1; // empty prefix sits just before index 0
long long running = 0;
int answer = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
running += nums[i];
auto it = firstIndex.find(running - (long long)k);
if (it != firstIndex.end()) answer = max(answer, i - it->second);
firstIndex.emplace(running, i); // emplace is a no-op if the key exists
}
return answer;
}
};emplace is doing real work here. Write firstIndex[running] = i instead and every repeat overwrites the earliest index with a later one, which quietly shortens every answer.
The map’s key is long long, matching the accumulator. It’s worth knowing why. If you declare the map with an int key while the running sum is long long, then find(running - k) narrows the argument silently — no warning, even under -Wall -Wextra. A wanted value of 2,500,000,000 arrives at the map as −1,794,967,296. On this problem the bounds save you: the prefix sums span at most about 2 × 109, and a truncated lookup would have to collide with a key roughly 232 away, which the array can’t reach. So the mismatch is latent rather than fatal here. It is still the wrong types, and it stops being latent the moment the code is reused somewhere with a longer array.
525. Contiguous Array (Medium)
The task: given an array of only zeros and ones, find the longest slice containing equally many of each.
There is no sum in this problem, which is exactly why it’s the most instructive one here. Re-encode until there is. Count a zero as −1 and a one as +1, and “equal numbers of each” becomes “these values sum to zero”, which becomes “the running total at both ends is the same”. A problem about counting turns into a problem you’ve already solved four times.
class Solution {
public:
int findMaxLength(vector<int>& nums) {
// balance -> the earliest index that produced it
unordered_map<int, int> firstIndex;
firstIndex[0] = -1;
int balance = 0;
int answer = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
balance += (nums[i] == 0 ? -1 : 1); // the re-encoding, in one line
auto it = firstIndex.find(balance);
if (it != firstIndex.end()) answer = max(answer, i - it->second);
else firstIndex[balance] = i; // only the first sighting counts
}
return answer;
}
};The else is the same “keep the earliest” rule as 325, written out longhand. When the balance is already in the map you’re reading, not writing, so there’s nothing to insert.
523. Continuous Subarray Sum (Medium)
The task: report whether any slice of length at least two has a sum that’s a multiple of k. Just true or false.
Residues again, earliest indices again, and one extra condition: the length floor. Two prefixes with the same residue that are adjacent describe a slice of length one, which doesn’t qualify.
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
// running sum % k -> the earliest index that produced it
unordered_map<int, int> firstIndex;
firstIndex[0] = -1;
long long running = 0;
for (int i = 0; i < (int)nums.size(); ++i) {
running += nums[i];
int residue = (int)(running % k);
auto it = firstIndex.find(residue);
if (it == firstIndex.end()) firstIndex[residue] = i;
else if (i - it->second > 1) return true; // length must be at least two
}
return false;
}
};Two contrasts with 974 are worth noticing. First, 974 could use a vector of size k because k was small; here k can be near the top of the 32-bit range, so a vector is out and a hash map is the only option. Second, this problem’s values are non-negative, so running % k is never negative and the guard 974 needed isn’t required. Both of those are constraint-dependent, not properties of the pattern.
The accumulator is long long even though the constraints promise the total fits in a signed 32-bit integer. Taking the free width is better than remembering the promise.
Complexity
Every solution above is a single pass. The table family costs O(n) or O(rows × cols) to build and O(1) per query afterwards, which is the entire point: you pay once so that a thousand queries cost a thousand subtractions instead of a thousand scans.
The streaming family is O(n) time with O(1) hash operations per element, amortized. Space is where they differ, and it tracks what’s being hashed: O(n) when the key is a raw sum (560, 325, 525), O(k) when the key is a residue and k is small enough to index directly (974), and O(1) when there are only two buckets (1524). 523 hashes residues but can’t bound them usefully, so it’s O(n) in the worst case.
Against the brute force, the saving is the inner loop. Enumerating every slice is n(n+1)/2 of them; at n = 2 × 104 that’s about 2 × 108 operations, which is roughly the whole budget before you’ve added anything up. Each of these runs in a few tens of thousands of steps instead.
Edge cases and common bugs
- Forgetting the empty prefix — no
freq[0] = 1orfirstIndex[0] = -1, and every slice that begins at index 0 is invisible. Small tests pass, because they usually have an answer somewhere in the middle. - Recording before looking up — in the counting family the current prefix then matches itself. On
[1]withk = 0that returns 1 instead of 0. Look up first, record second, always. - Negative remainders —
%in C++ follows the sign of the left operand, so a negative running total gives a negative residue. Used as a vector index that’s an out-of-bounds read; used as a hash key it splits one residue class into two. Addif (r < 0) r += k;. - Overwriting the earliest index — in the longest-slice family, plain
map[key] = ireplaces the first sighting on every repeat and shortens every answer. Useemplace, or guard the write with a lookup. - Key type narrower than the accumulator — a
long longrunning sum searched in anint-keyed map narrows silently, with no diagnostic under-Wall -Wextra. Keep the two types in step. - Dropping the length condition — 523 needs slices of length two or more. Without the
> 1test, any single element that happens to be a multiple ofkreturns true. - Assuming the sum fits — the table family’s ceiling is elements × largest value, and it’s a silent wrong answer when it’s wrong. Do the multiplication before you pick the type.
Inputs worth trying by hand: a single element; an array that is entirely zeros; k = 0 where the problem allows it; an array with no valid slice at all; and for anything with a modulus, an array whose running total goes negative.
Interview follow-ups
- “What if the array can be updated between queries?” — the prefix table dies, because one write invalidates every entry after it. That’s LeetCode 307, and the answer is a Fenwick tree or a segment tree: O(log n) per update and per query instead of O(1) and O(n).
- “What if all the values are positive?” — then the running sum is monotonic and a sliding window solves it in O(1) space. Being able to say why negatives break the window is the actual thing being tested.
- “Return the slice, not the count.” — store indices alongside the tally, and remember that a count question can have many answers while a longest question has a specific one.
- “Do 560 on a matrix.” — fix a pair of rows, collapse the columns between them into a single array of sums, and run 560 on it. O(rows² × cols), and it’s LeetCode 1074.
How to recognize it next time
Two triggers. If a problem asks the same range question repeatedly over data that never changes, build a table. If a problem says “subarray” or “contiguous” and asks how many, how long, or whether one exists, keep a running total and hash it.
When the quantity isn’t a sum, look for a re-encoding that makes it one, the way 525 turns zeros into −1. Counts of two things become a difference; “divisible by k” becomes a residue; “odd” becomes a single bit. The pattern is rarely hidden well.
This walkthrough follows a session deck on prefix sums by Joseph Choi; the code here has been rewritten in a single consistent style and the explanations are my own. Every solution above was compiled and run against the problems’ sample cases and the edge cases listed, with the undefined-behaviour and address sanitizers on. If something here is wrong or there’s a cleaner way to say it, leave a comment. More problems: the LeetCode series.