Subarray Sum Equals K
Learn prefix-sum counting by tracing prior cumulative totals, comparing brute force, and testing negatives and repeated prefixes in Python and TypeScript.
Understand the contract before choosing a data structure
Given an integer array nums and an integer k, return the number of contiguous non-empty subarrays whose elements sum exactly to k. Values may be positive, zero, or negative, so the method must remain correct even when the running sum does not move monotonically.
- Count contiguous subarrays, not arbitrary element pairs or subsequences.
- Different index ranges count as different subarrays even when they contain the same values.
- Negative numbers and zero are allowed, so a positive-only sliding-window assumption is not valid.
- Return the total number of matching index ranges rather than only whether one match exists.
nums = [1, 1, 1], k = 2Expected: 2
The ranges [0..1] and [1..2] both sum to 2, so repeated values create two distinct answers.
nums = [1, 2, 3], k = 3Expected: 2
Both [1, 2] and [3] are contiguous ranges whose sums equal 3.
Trace prefix sums before reading code
Trace input: nums = [1, 2, 3, -2, 2], k = 3; prefixCounts starts as {0: 1}. Read each card as the state before the current value is stored. That timing is the correctness invariant.
- Index
- 0
- Value
1- Needed
-2
{0: 1}Current prefix = 1. Prefix -2 has appeared 0 times, so total stays 0; then record prefix 1.
- Index
- 1
- Value
2- Needed
0
{0: 1, 1: 1}Current prefix = 3. Needed prefix 0 appeared once, so [0..1] is one valid subarray; total becomes 1.
- Index
- 2
- Value
3- Needed
3
{0: 1, 1: 1, 3: 1}Current prefix = 6. Needed prefix 3 appeared once, representing the boundary after index 1; [2..2] adds another match.
- Index
- 3
- Value
-2- Needed
1
{0: 1, 1: 1, 3: 1, 6: 1}Current prefix = 4. Needed prefix 1 appeared once, so the range [1..3] sums to 3; total becomes 3.
- Index
- 4
- Value
2- Needed
3
{0: 1, 1: 1, 3: 1, 6: 1, 4: 1}Current prefix = 6. Needed prefix 3 appeared once, so [2..4] is another match; total becomes 4 before prefix 6 is recorded again.
Can you defend the invariant?
Answer aloud before expanding each explanation. Syntax is not the test here; the mental model is.
Why does prefixCounts start with {0: 1} before any array element is processed?
- It reserves space for negative numbers.
- It represents the empty prefix so a subarray starting at index 0 can be counted.
- It forces the first element to be skipped.
- It prevents the running sum from becoming zero.
Answer: B. A current prefix equal to k needs an earlier prefix of 0. Seeding one empty prefix lets the algorithm count a valid range that begins at index 0 without a special case.
Why must the map store a frequency for each prefix sum instead of only remembering whether that prefix was seen?
- Frequencies make the array sorted.
- The same prefix can occur at multiple earlier boundaries, and each occurrence defines a distinct matching subarray.
- A set cannot store negative numbers.
- The frequency is needed only to calculate Big-O notation.
Answer: B. If currentPrefix - k occurred three times, there are three different earlier boundaries and therefore three distinct contiguous ranges ending at the current index.
Why is a normal positive-number sliding window unsafe for the general version of this problem?
- Sliding windows require strings.
- Negative values can make the sum decrease when the right edge expands or increase when the left edge moves, breaking the monotonic rule the window relies on.
- Sliding windows always use O(n²) time.
- Hash maps are required by the problem statement.
Answer: B. The usual shrink-when-too-large rule depends on positive values. With negatives, moving either boundary can change the sum in the opposite direction, so the decision rule is no longer reliable.
Translate the same invariant into two languages
Read the explanation after the code and point to the exact line that preserves each claim. If you cannot map reasoning to code, the implementation is still opaque.
Python
def subarray_sum(nums, k):
prefix = 0
total = 0
prefix_counts = {0: 1}
for value in nums:
prefix += value
total += prefix_counts.get(prefix - k, 0)
prefix_counts[prefix] = prefix_counts.get(prefix, 0) + 1
return total- prefix is the sum of every value processed so far.
- A previous prefix equal to prefix - k proves that the values after that boundary sum to k.
- The frequency map counts how many earlier boundaries have that prefix, so one step can contribute multiple matching subarrays.
- The lookup happens before the current prefix is recorded, which prevents a zero-length self-match when k = 0.
TypeScript
function subarraySum(nums: number[], k: number): number {
let prefix = 0;
let total = 0;
const prefixCounts = new Map<number, number>([[0, 1]]);
for (const value of nums) {
prefix += value;
total += prefixCounts.get(prefix - k) ?? 0;
prefixCounts.set(prefix, (prefixCounts.get(prefix) ?? 0) + 1);
}
return total;
}- The Map stores prefix-sum frequencies rather than array values or indices.
- prefix - k is the exact prior cumulative total needed to make the intervening range sum to k.
- The nullish fallback turns a missing prefix into zero matches without confusing a legitimate stored count.
- Recording the current prefix after the lookup preserves the boundary invariant and avoids counting an empty range.
Start every subarray and extend it
Choose each index as a possible start, then extend an end pointer to the right while maintaining a running sum.
Whenever that running sum equals k, increment the answer. This baseline is easy to verify because it enumerates every contiguous range exactly once.
The repeated rescanning makes the method quadratic even though it can use constant additional space, which is why prefix-sum reuse matters for larger inputs.
Complexity: O(n²) time and O(1) additional space when each starting index reuses one running sum.
Common mistakes are clues about the wrong mental model
Use a set instead of a frequency map
Repeated prefix sums represent different earlier boundaries. A set collapses them and undercounts cases where several subarrays end at the same index.
Record the current prefix before checking prefix - k
When k = 0, the current prefix would match itself and create a zero-length range that is not a valid non-empty subarray.
Use the positive-number sliding-window rule when negatives are allowed
Negative values break the monotonic relationship between moving a window boundary and increasing or decreasing the sum, so the usual shrink/expand decisions can skip valid ranges.
Forget the initial prefix count {0: 1}
Any valid subarray beginning at index 0 would have no earlier stored boundary and would be missed unless the empty prefix is represented.
Attack the algorithm, not just the happy path
A passing example only proves one path. These cases are chosen to challenge index identity, duplicates, and the arithmetic assumptions behind the lookup.
| Case | Input | Expected | Why it matters |
|---|---|---|---|
| Repeated values | [1, 1, 1], k 2 | 2 | Confirms that distinct index ranges are counted separately. |
| Whole prefix match | [3, 1, -1], k 3 | 2 | Confirms the seeded empty prefix counts a range that begins at index 0 while later repeated prefix sums can add another match. |
| Negative values | [1, -1, 0], k 0 | 3 | Confirms the method works when the running sum can move in both directions and when the same prefix repeats. |
| No match | [4, 5], k 3 | 0 | Confirms the frequency lookup contributes zero when the required earlier prefix never appears. |