Prefix sums
Precompute running totals so any range sum is one subtraction, and pair them with a hash map to count ranges.
Subarray Sum Equals K. Count the contiguous subarrays of nums whose sum is exactly k. Values may be negative.
Signals that point here
- Many range-sum queries on a fixed array.
- "Count subarrays with sum / xor / balance equal to k", especially with negative numbers.
- 2D: sum of a sub-rectangle (summed-area table).
The idea
Let P[j] be the sum of the first j elements. The subarray from i to j - 1 sums to P[j] - P[i]. So a subarray ending here sums to k exactly when some earlier prefix equals prefix - k.
Counting how many earlier prefixes had each value turns the search into a lookup. The sliding window fails here because negative numbers break monotonicity; this does not care.
def count_subarrays(nums: list[int], k: int) -> int:
seen = {0: 1} # prefix value -> how many times seen
prefix = count = 0
for x in nums:
prefix += x
count += seen.get(prefix - k, 0)
seen[prefix] = seen.get(prefix, 0) + 1
return countpublic static class PrefixSums
{
public static int CountSubarrays(int[] nums, int k)
{
var seen = new Dictionary<int, int> { [0] = 1 }; // prefix -> times seen
int prefix = 0, count = 0;
foreach (int x in nums)
{
prefix += x;
count += seen.GetValueOrDefault(prefix - k);
seen[prefix] = seen.GetValueOrDefault(prefix) + 1;
}
return count;
}
}Complexity
O(n) time and O(n) space. A plain prefix array for range queries is O(n) to build and O(1) per query.
Pitfalls interviewers watch for
- Forgetting the
{0: 1}seed, which misses every subarray that starts at index 0. - Updating
seen[prefix]before readingseen[prefix - k], which counts the empty subarray whenk = 0. - Integer overflow in C# on large inputs: say whether you need
long.
Variants worth knowing
- Range sum query: build
Ponce, answerP[r + 1] - P[l]. - Longest subarray with sum
k: store the first index of each prefix instead of a count. - Contiguous array with equal 0s and 1s: map 0 to -1 and look for prefix differences of 0.
Test it like the interviewer will
count_subarrays([1, 1, 1], 2)returns2count_subarrays([1, 2, 3], 3)returns2count_subarrays([1, -1, 0], 0)returns3count_subarrays([], 0)returns0- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: count_subarrays([3, 4, -7, 1, 3], 7)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Count subarrays whose sum is divisible by
k. - Find the longest subarray with equal numbers of 0s and 1s.
- Answer many sub-rectangle sum queries on a matrix in
O(1)each.
Check yourself
What identity does the pattern rest on?
The sum of nums[i..j-1] equals P[j] - P[i].
Why does a sliding window fail on this problem?
Negative values mean growing a window can lower its sum, so the window condition is not monotone.