Hashing and prefix sums

The hash map coding pattern and prefix sums, explained for interviews. How to spot them, a step-through of two sum and subarray sum, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems to practice.

Foundation14 min read

Find two numbers in an array that add up to a target. The first answer everyone reaches for is two loops: for each number, scan the rest for its partner. That is O(n²), and on 100,000 numbers it is ten billion comparisons. The inner loop keeps asking the same question, “is the number I need somewhere in here?”, and keeps answering it by looking at everything again.

A hash map answers that question in O(1). Walk the array once, and for each number ask the map whether its partner has already gone past. That is the whole pattern: spend memory to remember what you’ve seen, so you never search for it again. Prefix sums are the same idea applied to sums: remember the running total at every point, and the sum of any stretch becomes one subtraction.

How to spot it

Reach for a hash map when the problem has any of these:

A lookup inside a loop. “Find the pair”, “does the complement exist”, “first repeated element”. If your brute force has an inner loop that searches, a map can replace it.
Counting or grouping. Anagrams, frequencies, duplicates, “group these by”. The key is whatever the items share: sorted letters, a count signature, a remainder.
Sums over contiguous ranges. “Subarray sum equals k”, “range sum query”, “equal number of 0s and 1s”. That’s prefix sums, usually with a map of the prefixes seen so far.

And when it isn’t the right tool:

The input is already sorted. Two pointers finds pairs in O(1) memory, so a map wastes space (see two pointers).
You need order, not membership. A hash map can’t answer “the smallest key above 7”. That needs a sorted structure or a heap.

Watch it run

Step through two sum with a map. Here’s the point to notice. When a number arrives, its partner either already went past, and the map has it. Or it hasn’t arrived yet, and the partner will find this number in the map later. Either way, the pair is found exactly once, in one pass.

Then switch to Prefix sums, to count subarrays that sum to 3. The running total at each index is the sum of everything so far. A subarray ending here sums to 3 exactly when some earlier running total was 3 less than this one. So the map counts running totals, instead of trying every start.

nums (target 9)

30915211344

seen value → index

empty

seen = {} # value -> index
for i, number in enumerate(nums):
need = target - number
if need in seen:
return [seen[need], i]
seen[number] = i

Find two numbers that add up to 9. The map starts empty.

1 / 11

The template

Both functions in five languages. Each file runs its own checks, so you can paste it into an editor and run it.

Hashing.javaexample.pyHashing.csmain.goexample.ts

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Hashing {
    static int[] twoSum(int[] nums, int target) {
        // value -> index of every number already passed. One map lookup replaces the inner
        // loop that would scan for the complement: O(n) instead of O(n²).
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer partnerIndex = seen.get(target - nums[i]);
            // Checked before storing, so no self-pairs.
            if (partnerIndex != null) return new int[] {partnerIndex, i};
            seen.put(nums[i], i);
        }
        return new int[0];
    }

    static int subarraySum(int[] nums, int target) {
        // sum(i..j) == prefix[j] - prefix[i-1], so a subarray ending here
        // sums to target exactly when some earlier prefix equals total - target.
        // Count prefixes instead of trying every start.
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1); // the empty prefix, so subarrays starting at index 0 count too
        int total = 0, found = 0;
        for (int number : nums) {
            total += number;
            found += count.getOrDefault(total - target, 0);
            count.merge(total, 1, Integer::sum);
        }
        return found;
    }

    public static void main(String[] args) {
        check(Arrays.equals(twoSum(new int[] {3, 9, 5, 11, 4}, 9), new int[] {2, 4}));
        check(Arrays.equals(twoSum(new int[] {3, 3}, 6), new int[] {0, 1}));
        check(twoSum(new int[] {1, 2}, 7).length == 0);
        check(subarraySum(new int[] {1, 2, 1, -1, 2, 1}, 3) == 5);
        check(subarraySum(new int[] {1, -1, 0}, 0) == 3); // negatives rule out a sliding window
        System.out.println("ok: twoSum and subarraySum");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

A few details carry the correctness:

Look up before you store. In two sum, checking the map before adding number means a number can’t pair with itself. Store first, and [3] with target 6 wrongly returns [0, 0].
Seed the prefix map with {0: 1}. It stands for the empty prefix before index 0. Without it, a subarray that starts at index 0 and sums to target is never counted.
Count, don’t flag. In subarray sum, the same prefix total can occur more than once, and each occurrence is a different subarray. The map stores how many times, not just whether.

Choosing the key

Most hash map problems are really “what is the key?”.

Group anagrams works because every anagram shares a key. That key is its letters sorted ("eat" and "tea" both become "aet"), or its 26 letter counts as a tuple.
Continuous subarray sum works because two prefix sums with the same remainder mod k bracket a multiple of k. So the key is total % k.
Contiguous array (equal 0s and 1s) works once you count 0 as -1. Then equal halves become a zero-sum subarray, and that is subarray sum with target = 0.

Prefix sums without a map

When the array doesn’t change and you answer many range queries, a plain prefix array is enough. Build prefix with one extra slot so prefix[0] = 0, then every query is O(1):

prefix = [0]
for number in nums:
    prefix.append(prefix[-1] + number)

def range_sum(i: int, j: int) -> int:  # inclusive i..j
    return prefix[j + 1] - prefix[i]

The extra leading 0 is the same trick as {0: 1} above. It makes ranges that start at index 0 a normal case, instead of an edge case. Product of array except self is the multiplying cousin. It’s a prefix product from the left, times a suffix product from the right. There’s no division, so zeros are safe.

Complexity

	Time	Extra memory
Two sum with a map	O(n)	O(n)
Subarray sum equals k	O(n)	O(n)
Prefix array, then q range queries	O(n + q)	O(n)

Hash map operations are O(1) on average, not in the worst case. With a bad hash function, or inputs built to collide, they degrade toward O(n). Interviewers rarely push on this, but saying “average O(1)” shows you know.

Say this out loud

The brute force checks every pair, O(n²). The inner loop is only asking whether a value exists, so I’ll trade O(n) memory for a hash map and get O(n).

Interview questions

Interviewer asksTwo sum: what if the array is sorted, or you can't use extra memory?

Then use two pointers from both ends: O(n) time and O(1) memory if it’s sorted, O(n log n) if you sort it first. Sorting loses the original indexes, so if you must return them, sort pairs of (value, index) instead, which costs O(n) memory again.

Interviewer asksWhy does subarray sum equals k start the map with {0: 1}?

The map counts running totals seen before the current index. A subarray that starts at index 0 has no earlier total to subtract. So we pretend there was one: the empty prefix, with total 0, seen once. Without it, [3] with k = 3 would return 0.

Interviewer asksGroup anagrams: sort each word, or count letters?

Sorting each word costs O(L log L) for a word of length L. A 26-slot count costs O(L) and makes a key like a tuple of counts. Counting is asymptotically faster, but for short words sorting is simpler and fine. Say both, pick one, and note the counting key assumes lowercase English letters.

Interviewer asksWhat happens to a hash map's O(1) if every key collides?

Every key lands in one bucket and lookups become a scan, O(n) each. Java’s HashMap turns a long bucket into a balanced tree, so its worst case is O(log n). Python dicts and Go maps use randomized hashing so an attacker can’t easily pick colliding keys. In an interview, say “O(1) on average” and move on unless asked.

Practice

10 problems on LeetCode: 4 easy, 6 medium

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Use it when the brute force has an inner loop that searches, or the problem counts, groups or matches.
The idea: remember what you’ve seen in a map or set, so every later question is O(1).
The cost: O(n) memory, and no ordering.
Prefix sums: sum(i..j) = prefix[j+1] - prefix[i]. Pair them with a map of totals seen to count subarrays with a target sum in one pass, negatives included.
Remember: look up before you store, seed prefix maps with {0: 1}, and say “average O(1)”.