On this page
Description
Array hashing trades memory for time. As you walk the array once, you store what you've seen in a hash map or set. Then "have I seen the value that completes this one?" is an O(1) lookup instead of a rescan. It's the move behind Two Sum, finding duplicates and counting frequencies. With a running XOR or sum as the key, it also counts subarrays.
We'll go from simple to more technical:
- The pattern: check the map, then insert.
- A second flavor: prefix XOR with a hash map.
- Where the same lookup-instead-of-rescan runs in production.
- Choosing keys and values, and when sorting plus two pointers is the better trade.
The approach
Checking every pair for a target sum is O(n^2): each element scans all the later ones. You don't need to search for the partner, though. You only need to remember what you've already seen. For each element, work out its complement, target - value. Look it up in the map. Then store the element with its index.
Find two values that add up to 9 in [5, 8, 3, 6]:
| Index | Value | Complement | In the map? | Map after |
|---|---|---|---|---|
| 0 | 5 | 4 | no | {5: 0} |
| 1 | 8 | 1 | no | {5: 0, 8: 1} |
| 2 | 3 | 6 | no | {5: 0, 8: 1, 3: 2} |
| 3 | 6 | 3 | yes, at index 2 | found: indexes 2 and 3 |
Java
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
// found: seen.get(complement) and i
}
seen.put(nums[i], i);
}
Python
seen = {} # value -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
pass # found: seen[complement] and i
seen[x] = i
Check first, then insert. That way an element can never pair with itself, with no extra check needed.
A second flavor: prefix XOR + hash map
Some questions count instead of find. Count the subarrays whose XOR equals k keeps a running XOR and a map of how many times each XOR value has appeared so far:
Java
Map<Integer, Integer> countAtXor = new HashMap<>();
countAtXor.put(0, 1); // an empty prefix (XOR of nothing) is 0
int runningXor = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
runningXor ^= nums[i];
count += countAtXor.getOrDefault(runningXor ^ k, 0);
countAtXor.merge(runningXor, 1, Integer::sum);
}
Python
from collections import Counter
count_at_xor = Counter({0: 1}) # an empty prefix (XOR of nothing) is 0
running_xor = count = 0
for x in nums:
running_xor ^= x
count += count_at_xor[running_xor ^ k]
count_at_xor[running_xor] += 1
XOR undoes itself: a ^ a = 0. So if an earlier prefix had XOR runningXor ^ k, the elements between that prefix and here XOR to exactly k. Every such earlier prefix is a separate answer, which is why the map stores a count rather than one index. In [5, 3, 6, 5] with k = 6, it counts two subarrays: [5, 3] and [6].
Where you'll see it
"Has this webhook event ID been processed before?" is the same lookup. So is "have we seen this user or IP in the last N requests?" A cache is built on the same trade: spend memory to avoid repeating expensive work.
Which tool for which job?
| You need | Use |
|---|---|
| "Have I seen x before?" | a hash set |
| The index (or count) of what you've seen | a hash map |
| Counts of small integers (0..k) | a plain array of counts |
| A pair summing to a target, original indices | one pass: check, then insert |
| Subarrays with a given sum or XOR | running total as the key + a hash map |
| O(1) extra space, order can change | sort + two pointers |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Inserting before checking (Two Sum) | an element pairs with itself | check for the complement, then insert |
| Value as key with duplicates, no decision | the wrong index is kept | decide: first, last, or a list |
| No seed entry for the empty prefix | subarrays starting at 0 are missed | {0: 1} or {0: -1} |
| Mutating an object after using it as a key | the entry can't be found again | immutable keys (records, tuples) |
| A hash map when the values are small integers | extra memory and boxing | an array indexed by value |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Two Sum checks the map before inserting the current element. What breaks if you insert first?
Show answer
An element can pair with itself. If the target is exactly twice the element, the lookup finds the entry you just inserted, and the answer uses the same index twice.
2. The array has duplicate values, and you're building a value-to-index map. What decision do you have to make?
Show answer
Whether to keep the first index of a repeated value, the last one, or all of them. Each answers a different question. The problem decides which is right, not the map.
3. Counting subarrays by XOR stores a count per value. "The longest subarray summing to k" stored only the earliest index. Why the difference?
Show answer
They ask different things. The longest subarray needs the earliest match, because later matches only give shorter subarrays. "How many" needs every match, because each one is a separate subarray to count.
Key takeaways
- Check the map for the complement, then insert the current element. That order stops an element pairing with itself.
- With repeated values, decide what the map keeps: the first index, the last, or all of them.
- Prefix XOR plus a map counts subarrays with a given XOR. XOR undoes itself the way subtraction undoes a sum.
- Hashing spends O(n) memory for O(n) time. When memory matters more, sorting plus two pointers does the same job in O(n log n) time and O(1) space.