Prefix Sum + Hash Map: Counting Subarrays with a Target Sum

How many contiguous subarrays in a given array sum to exactly k? At first glance, you might try every possible subarray: pick a start index, pick an end index, sum the elements between them, and check. That brute-force approach runs in $O(n^2)$ time (or $O(n^3)$ without a running sum optimization), which falls apart on large inputs. The prefix sum + hash map technique solves this entire family of problems in $O(n)$ time, and once you internalize the core identity, it becomes one of the most versatile tools in your arsenal.

The Prefix Sum Identity

The key insight is a simple algebraic fact. Define prefix[j] as the sum of all elements from index 0 through index j. Then the sum of any subarray from index i to index j is:

sum(i..j) = prefix[j] - prefix[i - 1]

If you want that subarray sum to equal k, you need:

prefix[j] - prefix[i - 1] = k

Rearranging: prefix[i - 1] = prefix[j] - k

So as you scan through the array computing prefix sums, at each position j you ask: "Have I seen a prefix sum equal to prefix[j] - k before?" If yes, every occurrence of that earlier prefix sum represents a subarray ending at j that sums to exactly k.

Why a Hash Map Makes This $O(n)$

Without a hash map, you would need to scan all previous prefix sums for each new element, bringing you back to $O(n^2)$. But if you store every prefix sum you have seen so far in a hash map (with the count of how many times you have seen it), each lookup is $O(1)$. One pass through the array, one lookup per element, and you are done.

Walkthrough: nums = [1, 1, 1], k = 2

Let us trace through this example step by step. We start with prefix = 0 and a hash map initialized to {0: 1}.

• Index 0, num = 1: prefix becomes 1. We check for prefix - k = 1 - 2 = -1 in the map. Not found, so count stays at 0. We add prefix 1 to the map: {0: 1, 1: 1}.

• Index 1, num = 1: prefix becomes 2. We check for prefix - k = 2 - 2 = 0 in the map. Found with count 1, so count becomes 1. This corresponds to the subarray [1, 1] (indices 0 through 1). We add prefix 2 to the map: {0: 1, 1: 1, 2: 1}.

• Index 2, num = 1: prefix becomes 3. We check for prefix - k = 3 - 2 = 1 in the map. Found with count 1, so count becomes 2. This corresponds to the subarray [1, 1] (indices 1 through 2). We add prefix 3 to the map: {0: 1, 1: 1, 2: 1, 3: 1}.

Final answer: 2 subarrays sum to k = 2.

Why Initialize the Map with {0: 1}

This is easy to overlook. The initial entry {0: 1} handles the case where a subarray starting at index 0 sums to exactly k. When prefix[j] equals k, we need prefix[j] - k = 0 to exist in the map, and it only will if we seeded it there. Without this initialization, you would miss every subarray that starts at the beginning of the array.

Code: Subarray Sum Equals K

LeetCode 560 asks you to find, given an array of integers and a target k, the total number of subarrays whose sum equals k.

def subarraySum(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}
    for num in nums:
        prefix += num
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Five lines of logic. The elegance of this solution is that it handles negative numbers, zeros, and all edge cases without any special treatment.

Variation: Contiguous Array (Longest Subarray)

Consider LeetCode 525: you are given a binary array of 0s and 1s, and you need to find the longest contiguous subarray with an equal number of 0s and 1s. The trick is to convert every 0 to -1. Now the problem becomes: find the longest subarray with sum 0.

Apply the same prefix sum logic. If prefix[j] == prefix[i], then the subarray from i+1 to j has sum 0, which means equal 0s and 1s. Instead of counting occurrences, you store the first index where each prefix sum appeared. The length of the subarray is j - first_index, and you want to maximize that.

Walkthrough: nums = [0, 1, 0, 0, 1, 1, 0]

After converting 0s to -1s: [-1, 1, -1, -1, 1, 1, -1]. We track prefix sums and the first index where each appears:

• Index 0: prefix = -1. First time seeing -1, store index 0.
• Index 1: prefix = 0. We seeded 0 at index -1, so length = 1 - (-1) = 2. Max length = 2.
• Index 2: prefix = -1. Seen at index 0, so length = 2 - 0 = 2. Max stays 2.
• Index 3: prefix = -2. First time, store index 3.
• Index 4: prefix = -1. Seen at index 0, so length = 4 - 0 = 4. Max length = 4.
• Index 5: prefix = 0. Seen at index -1, so length = 5 - (-1) = 6. Max length = 6.
• Index 6: prefix = -1. Seen at index 0, so length = 6 - 0 = 6. Max stays 6.

The longest subarray with equal 0s and 1s has length 6.

def findMaxLength(nums):
    prefix = 0
    first_seen = {0: -1}
    max_len = 0
    for i, num in enumerate(nums):
        prefix += 1 if num == 1 else -1
        if prefix in first_seen:
            max_len = max(max_len, i - first_seen[prefix])
        else:
            first_seen[prefix] = i
    return max_len

Variation: Subarray Sum Divisible by K

For LeetCode 974, the problem asks for subarrays whose sum is divisible by k. The key change is using prefix_sum % k instead of the raw prefix sum. If two prefix sums have the same remainder when divided by k, the subarray between them has a sum divisible by k.

One subtlety: in Python, the modulo operator handles negative numbers correctly (it always returns a non-negative result), but in languages like Java or C++, you may need to adjust with ((prefix % k) + k) % k to avoid negative remainders.

def subarraysDivByK(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}
    for num in nums:
        prefix = (prefix + num) % k
        count += seen.get(prefix, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Count vs. Longest: A Subtle but Critical Difference

These problems split into two families, and the hash map stores different things depending on which you are solving:

• Count subarrays (Subarray Sum Equals K, Divisible by K): The map stores the frequency of each prefix sum. Every previous occurrence is a valid subarray, so you add the count.

• Longest subarray (Contiguous Array): The map stores the first index where each prefix sum appeared. You never overwrite it, because the first occurrence gives you the longest possible subarray ending at the current position.

Mixing these up is a common bug. If a problem asks "how many," use frequency. If it asks "longest" or "shortest," use first (or last) occurrence.

Variation: Find Pivot Index

Take LeetCode 724: find the leftmost index where the sum of elements to its left equals the sum of elements to its right. This is a pure prefix sum problem without the hash map. Compute the total sum once. Then scan left to right, maintaining a running left sum. At each index, the right sum is total - left_sum - nums[i]. If left equals right, return that index.

def pivotIndex(nums):
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total - left_sum - num:
            return i
        left_sum += num
    return -1

No hash map needed: the insight is that both sides of the pivot can be expressed in terms of a single running prefix sum and the precomputed total. This runs in $O(n)$ time and $O(1)$ space.

Variation: Maximum Size Subarray Sum Equals k

The problem LeetCode 325 asks for the longest subarray whose sum equals exactly k. This combines the prefix sum identity with the "first occurrence" hash map strategy from the Contiguous Array problem. Store the first index where each prefix sum appears. At each position, check whether prefix - k exists in the map, and if so, compute i - first_seen[prefix - k] as a candidate for the maximum length.

def maxSubArrayLen(nums, k):
    prefix = 0
    first_seen = {0: -1}
    max_len = 0
    for i, num in enumerate(nums):
        prefix += num
        if prefix - k in first_seen:
            max_len = max(max_len, i - first_seen[prefix - k])
        if prefix not in first_seen:
            first_seen[prefix] = i
    return max_len

The critical detail: never overwrite an existing entry in first_seen. The first time a prefix sum appears gives the longest possible subarray ending at any future index. This is the same reasoning as the Contiguous Array solution, but generalized to an arbitrary target sum.

Variation: Count Number of Nice Subarrays

With LeetCode 1248, you are given an array of integers and must count subarrays containing exactly k odd numbers. The trick is to reduce this to a problem you already know. Replace each element: odd becomes 1, even becomes 0. Now "count subarrays with exactly k odd numbers" becomes "count subarrays with sum exactly k," which is Subarray Sum Equals K.

def numberOfSubarrays(nums, k):
    count = 0
    prefix = 0
    seen = {0: 1}
    for num in nums:
        prefix += num % 2  # 1 if odd, 0 if even
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

This reduction pattern is broadly useful. Any time a problem asks you to count subarrays based on some property of individual elements, see if you can map each element to 0 or 1 (or another simple value) and restate the problem as a subarray sum problem. Binary Subarrays With Sum (LeetCode 930) works the same way: the array is already binary, so you apply the prefix sum + hash map template directly.

Variation: Product of Array Except Self

LeetCode 238 presents a different angle: return an array where each element is the product of all elements except the one at that index, without using division. This is a prefix/suffix product problem rather than a prefix sum problem, but the underlying idea is the same: precompute cumulative values from both directions and combine them.

Build a left product array where left[i] is the product of all elements before index i, and a right product array where right[i] is the product of all elements after index i. The answer at each index is left[i] * right[i].

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= nums[i]
    return result

The two-pass approach uses the output array itself for the left products, then multiplies in the right products on the second pass. This achieves $O(n)$ time and $O(1)$ extra space (beyond the output array). The pattern generalizes: whenever you need to combine information from "everything to the left" and "everything to the right" of each element, think prefix and suffix arrays.

Complexity Analysis

• Time: $O(n)$ for all variants. You make a single pass through the array, and each hash map operation is $O(1)$ amortized.
• Space: $O(n)$ in the worst case. The hash map can grow up to n distinct prefix sums, though in practice it is often smaller.

The prefix sum + hash map pattern is one of those techniques that, once learned, makes an entire category of problems feel routine. Any time you see "subarray," "contiguous," and "sum" in the same sentence, reach for this approach.

Recognizing this pattern

You're probably looking at prefix sum + hash map when:

• The words "subarray" or "contiguous" appear alongside "sum equals k," "divisible by k," "exactly k odd numbers," or "equal number of 0s and 1s."
• Values can be negative or zero, so a sliding window (which needs monotone shrinkage) does not work.
• The brute force is "for each pair (i, j), sum nums[i..j]," an $O(n^2)$ approach that you need to drop to $O(n)$.
• You're being asked to count matching subarrays, or to find the longest/shortest subarray meeting a sum condition.
• The condition can be rewritten as an equation between two prefix sums (prefix[j] - prefix[i] = k, prefix[j] ≡ prefix[i] (mod k), etc.).

Common templates:

• Count subarrays with sum k: map stores frequencies of prefix sums; add seen[prefix - k] at each step. Example: Subarray Sum Equals K.
• Subarrays divisible by k: map stores frequencies of prefix % k; equal remainders mean the gap is divisible. Example: Subarray Sums Divisible by K.
• Equal 0s and 1s (or any binary balance): remap 0 to -1 and look for two equal prefix sums. Example: Contiguous Array.
• Longest subarray with sum k: map stores first index of each prefix sum, never overwritten, maximize i - first_seen[prefix - k]. Example: Maximum Size Subarray Sum Equals k.
• Reduction to subarray sum: recode each element to 0/1 (or another scalar), then apply the count template. Example: Count Number of Nice Subarrays.