I Couldn't Count Subarrays Until I Thought About Handshakes

Hi everyone, I'm starting a series where I break down the core intuition behind coding patterns I've struggled to truly understand or reuse confidently. Not just the "how" but the "why does this actually work" part. Starting with one that tripped me up longer than I'd like to admit.

I Couldn't Count Subarrays Until I Thought About Handshakes

I understood the concept behind "Subarrays Divisible by K" for a while. Prefix sums, mod k, check for matching remainders. Cool. But every time I tried to write the actual counting logic, I'd freeze. Why does count += map[remainder] work? Why not count += 1? Where does the formula come from?

It finally clicked when I stopped thinking about arrays and started thinking about people in a room.

The gap in my understanding

Here's what I already knew: if two prefix sums have the same remainder when divided by k, the elements between them sum to a multiple of k. Standard prefix sum trick.

What I didn't get was the leap from "find matching remainders" to "count all valid subarrays." I could identify that a valid subarray existed, but not how to count all of them efficiently.

Turns out I was missing some pretty basic math.

Lesson 1: The Handshake Problem

5 people in a room. Everyone shakes hands with everyone else exactly once. How many handshakes?

The formula is n * (n-1) / 2. For 5 people, that's 10. But the formula alone wasn't what helped me. What helped was seeing it built incrementally:

• Person A enters. Nobody there. 0 handshakes.
• Person B enters. Shakes hands with A. +1.
• Person C enters. Shakes hands with A and B. +2.
• Person D enters. Shakes with A, B, C. +3.
• Person E enters. Shakes with A, B, C, D. +4.

Total: 0 + 1 + 2 + 3 + 4 = 10.

That's the same as 5×4/2 = 10. The incremental version and the formula give the same answer, just computed differently.

This is exactly what the hashmap does. When you write count += map[remainder], you're saying: "this new prefix sum just walked into the room. How many prefix sums with the same remainder are already here? Shake hands with all of them."

You don't add 1. You add however many are already waiting.

Lesson 2: Modular Arithmetic (Remainder Buckets)

When you divide any integer by k, the remainder is always between 0 and k-1. So every number falls into one of k "buckets."

The rule that matters: if two numbers have the same remainder mod k, their difference is always divisible by k.

14 % 5 = 4
 9 % 5 = 4
14 - 9 = 5   → divisible by 5 ✓

This works every time, not just with convenient examples. If a % k == b % k, then (a - b) % k == 0. Always.

This is why we care about prefix sum remainders. The subarray sum between index i and j is prefix[j] - prefix[i]. If both prefix sums land in the same remainder bucket, their difference (the subarray sum) is divisible by k.

Putting It Together

So the algorithm becomes:

1. Compute prefix sums and their remainders (that's the mod arithmetic)
2. Group them into remainder buckets
3. Count pairs within each bucket (that's the handshake problem)

The hashmap approach does step 3 incrementally. Here's a concrete walkthrough with arr = [4, 5, 0, -2, -3, 1], k = 5:

Start: map = {0: 1}   (prefix[-1] = 0, remainder 0)

i=0: prefix=4,  rem=4, map[4]=0  → count += 0, map={0:1, 4:1}
i=1: prefix=9,  rem=4, map[4]=1  → count += 1, map={0:1, 4:2}
i=2: prefix=9,  rem=4, map[4]=2  → count += 2, map={0:1, 4:3}
i=3: prefix=7,  rem=2, map[2]=0  → count += 0, map={0:1, 4:3, 2:1}
i=4: prefix=4,  rem=4, map[4]=3  → count += 3, map={0:1, 4:4, 2:1}
i=5: prefix=5,  rem=0, map[0]=1  → count += 1, map={0:2, 4:4, 2:1}

Total: 0 + 1 + 2 + 0 + 3 + 1 = 7

Look at remainder 4. It appeared 4 times total (at prefix indices 0, 1, 2, 4). The incremental additions for that bucket alone were 0, 1, 2, 3 which sums to 6. And 4×3/2 = 6. Same answer. The handshake formula, built up one step at a time.

The {0: 1} Seed

One thing that confused me initially: why do we start the map with {0: 1}?

Because there's a "virtual" prefix sum before index 0, which equals 0. If any prefix sum itself is divisible by k (remainder 0), it needs something to pair with. That virtual prefix[-1] = 0 is the pairing partner. Without it, you'd miss all subarrays that start from index 0.

Extending to "Subarray Sum Equals K" (LeetCode 560)

Once you get the divisible-by-k version, this one is a small twist. Instead of "same remainder," you look for a specific difference:

Divisible by K: prefix[j] % k == prefix[i] % k  →  look up same remainder
Sum Equals K:   prefix[j] - prefix[i] == k      →  look up (prefix[j] - k)

The code:

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

Same three ingredients: prefix sums give you the "what to track," the lookup condition tells you "what to search for," and the frequency map handles "how to count" (handshakes, not just existence).

Important: use a frequency dict, not a set. I made this mistake. A set only tells you "yes, it exists." A dict tells you "it exists 3 times," which means 3 valid subarrays, not 1. That's the handshake lesson all over again.

The Math Foundation I Was Missing

If you're stuck on these problems like I was, here's the learning order that worked for me:

1. Pair counting (n choose 2): Get comfortable with why "n people, count handshakes" = n(n-1)/2, and why building it as 0+1+2+...+(n-1) gives the same answer.

2. Modular arithmetic: Drill the rule "same remainder means difference is divisible by k" until it's automatic.

3. Connecting the two: Subarray problems ask you to count pairs of prefix sums that satisfy some condition. Once you see that, the hashmap is just the efficient way to count those pairs on the fly.

Problems to Practice

These all use the same pattern, roughly in order of difficulty:

• LeetCode 560 - Subarray Sum Equals K (the classic)
• LeetCode 974 - Subarrays Sums Divisible by K
• LeetCode 525 - Contiguous Array (convert 0s to -1s, then it's sum equals 0)
• LeetCode 1248 - Count Number of Nice Subarrays
• LeetCode 1010 - Pairs of Songs Divisible by 60 (pure remainder + pairs, no prefix)
• LeetCode 437 - Path Sum III (same technique, but on a tree)

The underlying skill isn't memorizing the prefix sum trick. It's recognizing when a subarray condition can be rewritten as a pairwise condition on prefix values, and then counting those pairs with a hashmap.

That recognition is what these problems are really testing.