Hash Maps and Prefix Sums

Updated Nov 19, 2026 · 4 min read
On this page

    Many array questions hide a nested loop: for each element, search the rest for something that fits. This pattern removes the inner loop. You walk the array once and keep a hash map of what you have already seen, so the "search" becomes a single O(1) lookup. Add a running total (a prefix sum) and the same trick answers questions about subarrays, not just pairs.

    If you have not read Hash Maps yet, start there: it covers how the map itself works. This page is about using it as a problem-solving pattern.

    When to recognise it

    • "Find two things that add up to / match / complement each other." The partner of x is target − x; ask the map whether you have seen it.
    • "Count / group by some key." Anagrams, frequencies, first unique character.
    • "Subarray whose sum is k", "longest subarray with equal 0s and 1s", "subarray sum divisible by k". The word subarray (contiguous) plus sum points to prefix sums.
    • Numbers can be negative. That rules out Sliding Window, whose shrink step assumes adding more never helps, and leaves prefix sums as the standard tool.
    • "Answer many range-sum queries on a fixed array." Build the prefix array once; each query is one subtraction.

    How it works

    Let prefix[i] be the sum of the first i numbers, with prefix[0] = 0. The sum of nums[l..r] is then prefix[r + 1] − prefix[l]. A subarray sum is the difference of two prefix sums.

    Two rows: nums [1, 2, 3, −2, 2] and prefix [0, 1, 3, 6, 4, 6]. The subarray [3, −2] sums to 1, which equals prefix 4 minus prefix 3.
    Two rows: nums [1, 2, 3, −2, 2] and prefix [0, 1, 3, 6, 4, 6]. The subarray [3, −2] sums to 1, which equals prefix 4 minus prefix 3.

    So "how many subarrays ending here sum to k?" becomes "how many earlier prefixes equal prefix − k?". Keep a map from prefix value to how many times you have seen it, and that question is one lookup.

    Template

    from collections import defaultdict
    
    def count_subarrays_with_sum(nums, k):
        """Prefix-sum template: how many contiguous subarrays add up to k."""
        seen = defaultdict(int)
        seen[0] = 1            # the empty prefix, so subarrays starting at index 0 count
        prefix = count = 0
        for x in nums:
            prefix += x
            count += seen[prefix - k]   # earlier prefixes that leave exactly k
            seen[prefix] += 1           # store AFTER the lookup
        return count

    Time O(n), space O(n). Two details carry the whole solution: the map starts as {0: 1}, and the lookup happens before the store.

    Step-by-step table for nums [1, 2, 3, −2, 2] with k = 3: at each step the prefix, the value we need (prefix − 3), how many times it was seen, and the map after storing. Total 4.
    Step-by-step table for nums [1, 2, 3, −2, 2] with k = 3: at each step the prefix, the value we need (prefix − 3), how many times it was seen, and the map after storing. Total 4.

    Variants

    Store the first index, not a count. For "longest subarray with property P", map each prefix value to the first index where it appeared, and never overwrite it. The classic example turns 0s into −1s, so "equal 0s and 1s" becomes "sum 0":

    def longest_balanced(bits):
        """Variant: longest subarray with equal 0s and 1s (store the FIRST index of each prefix)."""
        first = {0: -1}
        prefix = best = 0
        for i, b in enumerate(bits):
            prefix += 1 if b == 1 else -1
            if prefix in first:
                best = max(best, i - first[prefix])
            else:
                first[prefix] = i
        return best

    Static range sums. When the array never changes, a plain prefix list answers each query in O(1):

    def range_sum_builder(nums):
        """Static range sums in O(1) after O(n) setup: pre[i] = sum(nums[:i])."""
        pre = [0]
        for x in nums:
            pre.append(pre[-1] + x)
        return lambda l, r: pre[r + 1] - pre[l]   # inclusive l..r

    Divisible by k. Store prefix % k instead of prefix: two prefixes with the same remainder bound a subarray whose sum is a multiple of k. In Python % is already non-negative; in Java or C++ add k before taking the remainder again.

    Common bugs

    • Missing {0: 1}. Without the empty prefix, subarrays that start at index 0 are never counted.
    • Storing before looking up. With k = 0, the current prefix matches itself and you count an empty subarray at every step.
    • Overwriting the first index in the "longest" variant. Keep the earliest index; a later one can only give a shorter subarray.
    • Reaching for a sliding window with negative numbers. The window cannot decide when to shrink. Prefix sums do not care about signs.
    • Integer overflow in Java or C++ when sums get large. Use long.
    Two code boxes side by side: storing the prefix before the lookup (wrong, red) and looking up before storing (right, green). With k = 0 the wrong order matches each prefix with itself.
    Two code boxes side by side: storing the prefix before the lookup (wrong, red) and looking up before storing (right, green). With k = 0 the wrong order matches each prefix with itself.

    Say this in the interview

    • "A subarray sum is the difference of two prefix sums, so for each end position I need the number of earlier prefixes equal to prefix − k. A hash map gives me that in O(1), so the whole thing is O(n)."
    • "I seed the map with prefix 0 seen once, so a subarray that starts at the beginning counts."
    • "A sliding window won't work here because the numbers can be negative."

    Problems for this pattern

    Easiest first:

    1. Two Sum: the complement lookup in its purest form.
    2. Valid Anagram: count letters in one string, subtract the other.
    3. Group Anagrams: group by a computed key.
    4. Product of Array Except Self: prefix and suffix products, no division.
    5. Longest Consecutive Sequence: a set answers "is x − 1 here?" so each run is walked once.
    6. Subarray Sum Equals K: the template above.
    7. Insert Delete GetRandom O(1): a hash map of value to index plus an array, swap-with-last on delete.
    8. Logger Rate Limiter: a map from message to the last time it was printed.
    9. Find Duplicate File in System: group paths by file content as the key.
    10. Count Primes: a sieve, a boolean table filled in one pass.

    Related

    Hash Maps (the data structure) · Sliding Window (the alternative when all numbers are non-negative) · Two Pointers (the O(1)-space alternative when the array is sorted) · Pattern Recognition Cheat Sheet