Subarray Sum Equals K: Prefix Sums Meet Hash Maps

LeetCode #560, Subarray Sum Equals K, is one of those problems where a single insight transforms an O(n^2) brute force into a clean O(n) solution. The trick is combining prefix sums with a hash map that counts how many times each prefix sum has appeared. Once you see why it works, the code almost writes itself.

The problem

Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k.

nums = [1, 1, 1], k = 2  -> 2  (subarrays [1,1] starting at index 0 and index 1)
nums = [1, 2, 3], k = 3  -> 2  (subarrays [1,2] and [3])
nums = [1, 2, 3, -1, 1, 2], k = 3  -> 4

A subarray is a contiguous, non-empty sequence of elements within the array. Note that nums can contain negative numbers, which rules out certain approaches.

The approach

The key insight comes from prefix sums. Define prefix_sum[j] as the sum of elements from index 0 through index j. If prefix_sum[j] - prefix_sum[i] = k, then the subarray from index i+1 to index j has a sum of exactly k.

So the question becomes: for each position j, how many earlier positions i had a prefix sum equal to prefix_sum[j] - k? If you store the frequency of every prefix sum you have seen so far in a hash map, you can answer that question in O(1) for each j. One pass through the array, one hash map, and you are done.

The solution

from collections import defaultdict

def subarraySum(nums, k):
    prefix_count = defaultdict(int)
    prefix_count[0] = 1
    prefix_sum = 0
    count = 0

    for num in nums:
        prefix_sum += num
        count += prefix_count[prefix_sum - k]
        prefix_count[prefix_sum] += 1

    return count

Here is how it works:

1. Seed the map with {0: 1}. Before processing any element, the prefix sum is 0. If the running prefix sum ever equals k, then prefix_sum - k = 0, and we need the map to report that 0 has been seen once. Without this seed, we would miss subarrays that start from the very beginning of the array.

2. Compute the running prefix sum. For each element, add it to the running total.

3. Check for prefix_sum - k in the map. If some earlier prefix sum equals prefix_sum - k, then the subarray between that earlier position and the current position sums to k. The frequency in the map tells you exactly how many such subarrays end here.

4. Record the current prefix sum. Increment its count in the map. This makes it available for future elements to reference.

The order matters: you check the map before updating it. This ensures you never count a "subarray" of length 0 (comparing a prefix sum against itself).

Step-by-step walkthrough

The algorithm finds all four subarrays that sum to 3: [1, 2], [3], [3, -1, 1], and [-1, 1, 2] (which has prefix sum difference 8 - 5 = 3).

Complexity analysis

Time: O(n). You iterate through the array once. Each hash map lookup and insertion is O(1) on average, so the total work is linear.

Space: O(n). In the worst case, every prefix sum is distinct and the map holds n + 1 entries. The prefix sums can range widely when the array contains both positive and negative numbers, but there are at most n + 1 distinct prefix sums (one for each position plus the initial 0).

The building blocks

Prefix sum + hash map pattern

This problem is a textbook example of the prefix sum + hash map combination. The idea is always the same: you are looking for subarrays whose sum satisfies some condition, and you can reframe that condition as a relationship between two prefix sums. The hash map lets you check that relationship in constant time.

The pattern shows up in several variations. In Contiguous Array (LeetCode #525), you store the first index where each prefix sum appears and look for repeated prefix sums (equivalent to k = 0 after a transformation). In Continuous Subarray Sum (LeetCode #523), you store prefix sum remainders and check divisibility. The core mechanic is identical: store prefix sum information, query it in O(1).

Edge cases

• All zeros with k = 0. Every single element and every contiguous group of elements sums to 0. The number of subarrays is n * (n + 1) / 2. The prefix sum stays at 0, and the hash map frequency keeps climbing.
• Negative numbers. The prefix sum can go up and down, and the same prefix sum value can appear multiple times. The frequency-based map handles this correctly because each occurrence creates a different subarray.
• k = 0. You are counting subarrays with sum 0. The algorithm checks how many times the current prefix sum has already been seen, which is exactly the number of subarrays ending here with sum 0.
• Single element equal to k. The prefix sum after that element minus 0 (the seed) equals k. The map reports one match. Works correctly.
• Single element not equal to k. The prefix sum minus k is not in the map. No match is counted.
• Entire array sums to k. The final prefix sum equals k, and k - k = 0 is in the map (from the seed). This subarray is counted.

From understanding to recall

The prefix sum + hash map pattern is elegant and compact: just four lines inside the loop. But remembering the details matters. You need to seed the map with {0: 1}. You need to check the map before updating it. You need to use a frequency count (not first occurrence) because this problem asks "how many" rather than "how long."

Spaced repetition drills these details into muscle memory. After a few review sessions, you will write the solution from memory and catch the subtle differences between this problem and its cousins (Contiguous Array, Continuous Subarray Sum). That is the gap between recognizing a pattern and executing it under pressure.

Related posts

• Two Sum - Same hash map pattern but looking for pairs instead of subarrays
• Contiguous Array - Another prefix sum + hash map problem where k is implicitly 0
• Continuous Subarray Sum - Similar prefix sum technique but checking divisibility by k instead of exact equality

CodeBricks uses spaced repetition to help you internalize patterns like prefix sum + hash map. Instead of re-reading solutions, you practice writing them from scratch at increasing intervals. Each review strengthens the neural pathways that connect "subarray sum" to "prefix sum map." Over time, the pattern becomes second nature.