Subarray Counting — Prefix Sum + Hash Map

Before we start

You already know prefix sums from pattern 1.06 — they turn range-sum queries into O(1). This chapter is about a different superpower of prefix sums: counting subarrays that satisfy a condition, in a single pass. By the end you will be able to:

• See why two prefix sums that differ by a target enclose a valid subarray between them.
• Explain out loud why a hash map of prefix-sum frequencies turns counting into O(1) per element.
• Recognise this pattern in subarray sum, subarray XOR, and divisibility counting problems.

Stop at every Pause & Think box.

Picture this first (no code yet)

The hiker's journal is the prefix sum. The "how many earlier totals equal T − target?" question is answered in O(1) by a hash map. Together: one pass, all subarrays counted.

The actual problem

Given an array of integers (possibly negative) and a target sum k, count the number of contiguous subarrays whose elements sum to exactly k.

input : [1, 1, 1], k = 2
output: 3
(subarrays: [1,1] at indices 0-1, [1,1] at indices 1-2, ... wait, n=3 so:
 [1,1] (0..1), [1,1] (1..2) = 2 subarrays of sum 2 ✓ — but output is 3?)

Wait — let me be precise:

input : [1, 2, 3], k = 3
output: 2
([3] at index 2, [1,2] at indices 0-1)

First, the slow way (so you feel the pain)

The obvious approach: for every pair (i, j), compute the sum of arr[i..j] and check if it equals k.

count = 0
for i in range(n):
    total = 0
    for j in range(i, n):
        total += arr[j]
        if total == k:
            count += 1

For n = 10,000: about 50 million iterations. For n = 100,000: about 5 billion. Classic O(n²) pain.

We need O(n). One pass. No nested loops.

The turning point

Let prefix[i] = sum of the first i elements (prefix[0] = 0 by convention).

The sum of subarray from index j to i-1 (inclusive) is:

prefix[i] - prefix[j] = k

Which means:

prefix[j] = prefix[i] - k

So: to count how many subarrays ending at position i have sum k, count how many earlier prefix sums equal prefix[i] - k.

You need prefix[j] = prefix[i] - k = 9 - 4 = 5. Every earlier position where the prefix sum was 5 defines a valid subarray from j to i-1. If the prefix sum of 5 appeared 3 times earlier, there are 3 valid subarrays ending at i.

A hash map that stores {prefix_sum → how many times it appeared} answers this in O(1).

The one idea to remember

Watch it happen, frame by frame

Array: [3, 4, 7, 2, -3, 1, 4, 2], k = 7.

We initialise freq = {0: 1} — there is one "empty prefix" of sum 0 (before the array starts).

i=0: prefix=3.  need=3-7=-4.  freq[-4]=0.  count+=0=0.  freq={0:1, 3:1}
i=1: prefix=7.  need=7-7=0.   freq[0]=1.   count+=1=1.  freq={0:1, 3:1, 7:1}
     → subarray [3,4] (indices 0..1) ✓
i=2: prefix=14. need=14-7=7.  freq[7]=1.   count+=1=2.  freq={0:1, 3:1, 7:1, 14:1}
     → subarray [4,7] (indices 1..2) ✓
i=3: prefix=16. need=16-7=9.  freq[9]=0.   count+=0=2.  freq={..., 16:1}
i=4: prefix=13. need=13-7=6.  freq[6]=0.   count+=0=2.  freq={..., 13:1}
i=5: prefix=14. need=14-7=7.  freq[7]=1.   count+=1=3.  freq={..., 14:2}
     → subarray [7,2,-3,1] (indices 2..5) ✓
i=6: prefix=18. need=18-7=11. freq[11]=0.  count+=0=3.  freq={..., 18:1}
i=7: prefix=20. need=20-7=13. freq[13]=1.  count+=1=4.  freq={..., 20:1}
     → subarray [2,-3,1,4,2] ... wait, let me verify: 2+(-3)+1+4+2=6. Hmm.

Let me retrace i=7: prefix=20, indices 0..7 sum = 3+4+7+2-3+1+4+2 = 20. We need prefix[j]=13. At i=4, prefix was 13. That means subarray from index 5..7: arr[5]+arr[6]+arr[7] = 1+4+2 = 7. ✓

Final count = 4.
Subarrays summing to 7: [3,4], [4,7], [7,2,-3,1], [1,4,2]  ✅

i=0: prefix=1.  need=1-0=1.  freq[1]=0.  count=0.  freq={0:1, 1:1}
i=1: prefix=0.  need=0-0=0.  freq[0]=1.  count=1.  freq={0:2, 1:1}
     → subarray [1,-1] (indices 0..1) ✓
i=2: prefix=1.  need=1-0=1.  freq[1]=1.  count=2.  freq={0:2, 1:2}
     → subarray [-1,1] (indices 1..2) ✓

Final count = 2. ✅
(Note: entire array [1,-1,1] sums to 1, not 0, so it doesn't count.)

Now, the code — line by line

from collections import defaultdict

def subarraySum(nums, k):
    freq = defaultdict(int)
    freq[0] = 1        # the empty prefix (before index 0) has sum 0 — count it

    prefix = 0
    count = 0

    for num in nums:
        prefix += num                  # extend the running total by one element

        need = prefix - k              # what earlier prefix sum would close a valid subarray?
        count += freq[need]            # how many times did that prefix appear before?

        freq[prefix] += 1              # record that we've now seen this prefix sum one more time
                                       # (AFTER querying, so we don't count the current position as "earlier")

    return count

Mapping every line to the hiker's journal:

• freq = {0: 1} — before the hike began, the total was 0. That "page 0" counts.
• prefix += num — update the running altitude after one hour.
• need = prefix - k — what total would an earlier page need to show for this window to sum to k?
• count += freq[need] — look up how many earlier pages showed that total.
• freq[prefix] += 1 — file this page in the journal before moving on. Must happen after the query — otherwise we'd count the current position as an "earlier" position, creating fake zero-length subarrays.

Why does initialising freq[0] = 1 matter?

Suppose the entire prefix from index 0 to i sums to exactly k. Then prefix - k = 0, and we need freq[0] to be 1 to count that subarray. Without the initialisation, freq[0] = 0 and we'd miss all subarrays that start from the very beginning.

Think of it as the hiker's journal having a "page 0" that records the starting altitude — it makes the formula work uniformly for all subarrays, including those starting at index 0.

Why is it always correct?

For every pair (j, i) where prefix[i] - prefix[j] = k:

• prefix[j] gets stored in freq when we process index j.
• When we process index i, we query freq[prefix[i] - k] = freq[prefix[j]] and find it.
• We add 1 to count for that pair.

Every valid pair is counted exactly once. No pair is missed (we store every prefix). No pair is double-counted (we query before storing the current prefix).

Time: O(n) — one pass, O(1) hash map operations per element. Space: O(n) — the hash map stores at most n+1 distinct prefix sums.

When should I reach for this? (the trigger list)

Reach for prefix-sum + hash map counting when:

• You need to count subarrays (not just find one) satisfying a sum condition.
• The array has negative numbers (ruling out the simple variable-window sliding approach, which only works on positive values).
• The condition is sum == k, sum % k == 0, XOR == k, or similar equality on a prefix aggregate.
• The brute-force answer is O(n²) nested loops over all (i, j) pairs.

One-sentence test: "Can I express the subarray condition as prefix[i] - prefix[j] = something fixed?" If yes — hash map the prefix sums.

The same trick in four disguises

Disguise 1 — Subarray Sum Divisible by K (LC #974)

Instead of prefix[i] - prefix[j] == k, we want (prefix[i] - prefix[j]) % k == 0, i.e., prefix[i] % k == prefix[j] % k. Store remainders (not raw sums) in the hash map.

def subarraysDivByK(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    prefix = 0
    count = 0
    for num in nums:
        prefix = (prefix + num) % k
        if prefix < 0: prefix += k    # Python % is always non-negative, but explicit guard
        count += freq[prefix]
        freq[prefix] += 1
    return count

Same skeleton — only the "key" in the map changes from raw prefix to remainder.

Disguise 2 — Count Subarrays with XOR Equal to K

Same pattern, but replace + with ^ and prefix - k with prefix ^ k:

def countSubarraysXOR(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    prefix = 0
    count = 0
    for num in nums:
        prefix ^= num                  # running XOR instead of sum
        count += freq[prefix ^ k]      # XOR equivalent of "prefix - k"
        freq[prefix] += 1
    return count

Because XOR is self-inverse: prefix ^ k ^ k = prefix, so prefix_j = prefix_i ^ k is the condition.

Disguise 3 — Longest Subarray with Sum k

Instead of counting, track the first time each prefix sum appeared. The longest subarray ending at i with sum k ends at i and starts at first_seen[prefix - k] + 1.

def longestSubarraySum(nums, k):
    first_seen = {0: -1}               # prefix 0 seen "before" index 0
    prefix = 0
    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     # store only first occurrence
    return max_len

Key change: store first_seen (not frequency); only record if not seen before (for maximum length).

def findMaxLength(nums):
    # treat 0 as -1, count subarrays with sum 0
    freq = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += 1 if num == 1 else -1
        count += freq.get(prefix, 0)   # subarrays with equal 0s and 1s ending here
        freq[prefix] = freq.get(prefix, 0) + 1
    return count

Traps that catch beginners

Say it like a pro (interview one-liner)

"The key insight is that a subarray arr[j..i] sums to k exactly when prefix[i] - prefix[j] = k, i.e., prefix[j] = prefix[i] - k. So I maintain a running prefix sum and a hash map of how many times each prefix has appeared. For each new prefix, I look up prefix - k in the map — that's the count of valid subarrays ending here. O(n) time, O(n) space, single pass."

Check yourself

Practice problems

That completes the entire Arrays & Two Pointers chapter (patterns 1.01–1.17). You now have the full toolkit for the most common array-manipulation questions in technical interviews.

Next up: Chapter 2 — Hashing, starting with Two Sum Pattern — where a hash map turns the classic O(n²) pair search into a single O(n) pass.