Hashing for Subarray Problems

Before we start

Pattern 1.17 introduced the core mechanic: prefix sum + hash map = O(n) subarray counting. If you haven't read it, read it first — it has the full story, the frame-by-frame trace, and the correctness proof.

This chapter focuses on one skill that 1.17 didn't drill: deciding what to hash. The prefix sum is just one option. Depending on the problem's condition, you'll hash:

• A running sum → for sum equals k
• A running XOR → for XOR equals k
• A running remainder mod k → for divisibility
• A running balance counter → for equal 0s and 1s

By the end you will be able to:

• Choose the right aggregate to hash for any subarray condition.
• Write the correct need = f(prefix) query for each variant.
• Distinguish count mode (frequency map) from longest mode (first-seen index map).

The one design question

Every problem in this family reduces to one question:

Two positions i and j define a valid subarray if aggregate[i] ○ aggregate[j] = target.
What is ○ and what is aggregate?

Once you answer that, the code is always the same skeleton:

freq = {identity: 1}   # identity element for the aggregate operation
agg = identity
count = 0

for x in arr:
    agg = combine(agg, x)         # extend the running aggregate
    need = inverse(agg, target)   # what earlier aggregate would complete the pair?
    count += freq.get(need, 0)    # how many times has that aggregate appeared?
    freq[agg] = freq.get(agg, 0) + 1

The three variants below differ only in combine, inverse, and identity.

The turning point — the hiker's balance story

This story is about sums. But the same hiker logic applies if the notebook tracks XOR values, remainders, or character balances — just change what she writes on each page.

The one idea to remember

Variant 1 — Sum equals k (the foundation)

Condition: prefix[i] - prefix[j] = k → need: prefix[i] - k

from collections import defaultdict

def subarraySum(nums, k):
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        count += freq[prefix - k]
        freq[prefix] += 1
    return count

combine = +, inverse = subtract k, identity = 0.

Variant 2 — XOR equals k

Condition: prefix_xor[i] ^ prefix_xor[j] = k
XOR is self-inverse: prefix_xor[j] = prefix_xor[i] ^ k → need: prefix_xor[i] ^ k

def subarrayXOR(nums, k):
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix XOR = 0
    prefix = 0
    count = 0
    for num in nums:
        prefix ^= num                  # XOR instead of add
        count += freq[prefix ^ k]      # need = prefix ^ k  (because x ^ k ^ k = x)
        freq[prefix] += 1
    return count

combine = ^, inverse = XOR with k, identity = 0.

Variant 3 — Sum divisible by k

Condition: (prefix[i] - prefix[j]) % k = 0 → prefix[i] % k = prefix[j] % k
Need: the same remainder as the current prefix.

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's % is always ≥ 0, but explicit guard for clarity
        count += freq[prefix]      # need = same remainder (not prefix - k!)
        freq[prefix] += 1
    return count

combine = (sum) % k, inverse = same value, identity = 0.

The key shift: we no longer store the raw prefix sum — we store the remainder. Two positions with the same remainder define a subarray divisible by k.

prefix sums:    4,  9,  9,  7,  4,  5
remainders:     4,  4,  4,  2,  4,  0

Remainder 4 appears 4 times → C(4,2) = 6 pairs (each pair of indices is a valid subarray).
Remainder 0 appears 1 time → 1 pair with the initial freq[0]=1.
Answer: 7  ✅ (matches LC #974)

Variant 4 — Equal 0s and 1s (LC #525)

Encoding trick: replace 0 with -1. Now "equal 0s and 1s" means "subarray sums to 0".
Run Variant 1 with k = 0.

def findMaxLength(nums):
    # encode 0 → -1, then 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)
        freq[prefix] = freq.get(prefix, 0) + 1
    return count

The encoding is the entire insight. Once encoded, it's identical to Variant 1 with k=0.

Count mode vs Longest mode

Everything above is count mode — use a frequency map, accumulate count += freq[need].

For longest subarray, switch to a first-seen index map and take max(length):

def longestSubarraySum(nums, k):
    first_seen = {0: -1}          # prefix sum → first index it appeared
    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     # only store FIRST occurrence
    return max_len

Key differences:

The "only if not yet in map" rule is critical for longest: you want the earliest occurrence to maximise the subarray length.

The decision table

All five share the same skeleton. The only changes are one line (combine) and one line (need).

Common traps

Say it like a pro (interview one-liner)

"This is a prefix-aggregate + hash map problem. I maintain a running aggregate and store how often each value has appeared. For each new position, I query 'has the complementary aggregate appeared before?' — answering in O(1). The only design choice is the right aggregate and its inverse. O(n) time, O(n) space, one pass."

freq = {identity: 1}
agg = identity
for x in arr:
    agg = combine(agg, x)
    count += freq[need(agg, target)]   # query FIRST
    freq[agg] += 1                     # store AFTER

Check yourself

Practice problems

Next up: Rolling Hash / Rabin-Karp — where a hash value slides across a string in O(1) per step, enabling pattern matching in O(n) time.