Subarray Sum Equals K

Learning goal: Recognize what must be counted and why a linear-time strategy is needed.

Core idea We need to count every contiguous range whose elements sum to k. A direct check of all subarrays can take quadratic time, which is too slow for large inputs. Because values may be negative, a sliding window cannot safely decide whether to expand or shrink.

Algorithm plan

• Scan the array from left to right.
• Maintain a running prefix sum called current.
• Use a frequency map to remember how often each earlier prefix sum occurred.
• Add the number of earlier prefixes equal to current - k.

Micro-example For nums = [1, 2, 1, 2] and k = 3, the answer is 3. The matching ranges are indices 0..1, 1..2, and 2..3.

Pitfalls

• Do not assume all numbers are positive.
• Count occurrences of a prefix, not just whether it exists.
• Initialize the map before processing the first element.

Recap

• The task is a counting problem over contiguous ranges.
• Prefix sums turn each range sum into a difference of two prefixes.
• Hashing makes the needed lookup constant time on average.

Learning goal: Derive the exact prefix value that identifies a subarray ending at the current index.

Core idea Let prefix[j] be the sum of the first j elements. The sum from index i through index j - 1 is prefix[j] - prefix[i]. Therefore, a subarray ending just before the current prefix position sums to k exactly when an earlier prefix equals current - k.

Recurrence

For the current prefix sum current:

newMatches = frequency[current - k]

Then record the current prefix for future subarrays:

frequency[current] += 1

The ordering matters: query the earlier-prefix map first, then add the current prefix. The initial empty prefix has sum 0, so the map starts with frequency[0] = 1.

Micro-example Suppose current = 3 and k = 3. We need an earlier prefix of 0. That represents a subarray starting at index 0 and ending here.

Pitfalls

• Using current + k instead of current - k reverses the equation.
• Replacing frequencies with a set loses multiple valid starting points.
• Updating the map before querying can incorrectly count an empty range when k = 0.

Recap

• A range sum is a difference between two prefix sums.
• Search for current - k.
• Frequencies count how many valid starts produce each ending position.

Learning goal: Translate the prefix-sum identity into a reliable one-pass algorithm.

Core idea The map represents all prefix sums strictly before the current position. At each element, extend the running prefix, ask how many earlier prefixes would make the difference equal k, and add that count to the answer. Only after the lookup do we store the new prefix.

Algorithm plan

1. Set answer = 0 and current = 0.
2. Seed frequency with {0: 1} for the empty prefix.
3. For each value x in nums, update current += x.
4. Add frequency.get(current - k, 0) to answer.
5. Increment frequency[current].
6. Return answer after the scan.

frequency = {0: 1}
current = answer = 0
for x in nums:
    current += x
    answer += frequency.get(current - k, 0)
    frequency[current] = frequency.get(current, 0) + 1
return answer

The map is a frequency table, not merely a membership set. Equal prefix sums can occur repeatedly, especially when zeros or positive and negative values cancel.

Micro-example For [1, 2, 1, 2], the running prefixes are 1, 3, 4, 6. At prefix 3, the needed value is 0, so the seeded entry finds [1, 2].

Pitfalls

• Query before recording the current prefix.
• Use an integer answer because many subarrays may match.
• Preserve the full prefix sum; do not reset it when it exceeds k.

Recap

• One pass maintains current, frequency, and answer.
• Lookup precedes insertion.
• The seed handles index-zero subarrays.

Learning goal: Trace every map lookup and update on one complete input.

Core idea We will use nums = [1, 2, 1, 2] and k = 3, the first example from the problem statement. The map always contains prefix sums from positions before the current element, along with how many times each sum has appeared.

Data structure model

The state has three parts:

Start with current = 0, answer = 0, and frequency = {0: 1}. The first 0 is an artificial prefix before index 0; it represents choosing a subarray start immediately before the array.

Micro-example At index 1, current = 3. Since current - k = 0 and frequency[0] = 1, one new subarray ends at index 1: [1, 2]. Later, repeated prefix values can produce additional matches because each occurrence represents a distinct start.

Pitfalls

• At index 0, do not forget that the seeded zero may create a match.
• The map shown after each step includes the current prefix for future steps.
• A single step may add zero, one, or several matches.

Recap

• Every index contributes through one needed-prefix lookup.
• The example produces additions of 0, 1, 1, and 1.
• The final total is 3.

Learning goal: Prevent the initialization and ordering mistakes that most often break this solution.

Core idea The frequency map is a record of possible starting boundaries. It must include the boundary before index 0, and it must preserve repeated prefix sums. These details are what allow the same algorithm to handle zeros, negative numbers, and ranges beginning at the first element.

Data structure model

Think of each map entry as a boundary counter:

For example, with [1, 2] and k = 3, the prefix becomes 3 at the second element. Without frequency[0] = 1, the algorithm reports zero instead of one.

Micro-example With nums = [1, -1, 1] and k = 0, repeated or changing prefixes must remain available. The first two values produce the valid range [1, -1].

Pitfalls

• Do not use a set: repeated prefix sums represent different starts.
• Do not clear the map when the running sum crosses k.
• Do not insert before querying, especially when k = 0.
• Use sufficiently wide integer arithmetic when the language requires it.

Recap

• Seed {0: 1} before the loop.
• Query first, then increment the current prefix frequency.
• Negative values and zeros require no special cases.

Learning goal: Justify the O(n) time and O(n) space bounds and retain the reusable pattern.

Core idea The algorithm performs one constant-average-time hash-map lookup and one update for each array element. It never revisits a subarray or rescans a prefix, so the total work grows linearly with n. The map can store one entry for each distinct prefix sum.

Algorithm plan

• Initialize current, answer, and frequency.
• Scan each value once.
• Query frequency[current - k].
• Add the frequency to answer.
• Record current for future positions.
• Return answer.

Micro-example For n = 4, the walkthrough makes four iterations and performs a bounded amount of map work per iteration. The map contains at most five prefix entries in that example, including the initial zero.

Pitfalls

• Average O(1) map operations assume a well-behaved hash table.
• Space is O(n) even if the final answer is small.
• The target k does not need to be positive.

Recap

• Time: O(n) average.
• Space: O(n).
• Reusable pattern: count earlier prefix sums equal to current - target.