The Complement Trick
The single most common hashing pattern: remember what you've seen so each element's partner is an O(1) lookup away.
On this page
If there's one hashing pattern to burn into memory, it's this one: as you scan, remember what you've seen, so that for each new element you can instantly ask "have I already seen the partner I need?" It's the trick behind two-sum and a dozen variations, and it's the canonical way to remove a nested loop.
Remember, then look up
The brute force for "find two numbers that sum to a target" checks every pair - O(n²). The complement
trick makes it one pass: for each number x, its partner must be target - x (its complement). If
you've stored every earlier number in a hash map, checking for that complement is O(1):
// two sum (unsorted) — O(n) time, O(n) space
int[] twoSum(int[] a, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value → index
for (int i = 0; i < a.length; i++) {
int need = target - a[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(a[i], i); // remember for future partners
}
return new int[]{-1, -1};
}Notice this is the unsorted counterpart to the two-pointer two-sum from the arrays module. Two pointers needs sorted input and O(1) space; the complement trick works on unsorted input at the cost of O(n) space. Recognizing which to use is a common decision: is it already sorted?
The pattern generalizes
The shape - "for each item, is its required partner already remembered?" - covers far more than sums:
- Contains a pair with difference k - remember values, check for
x - kandx + k. - Subarray sum equals k - remember prefix sums, check for
prefix - k(the prefix-sums lesson). - Longest consecutive sequence - put all numbers in a set, and only start counting a run from a number whose predecessor is absent, giving O(n).
// longest consecutive sequence — O(n) using a set of all values
int longestConsecutive(int[] a) {
Set<Integer> set = new HashSet<>();
for (int x : a) set.add(x);
int best = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // only start a run at its beginning
int len = 1;
while (set.contains(x + len)) len++; // extend forward
best = Math.max(best, len);
}
return best;
}Store as you go, not all up front
For two-sum, add each number to the map after checking for its complement, not before - otherwise an element could match itself (e.g. target 6 with a single 3). Building the map incrementally, using only earlier elements, also naturally returns the two distinct indices. The order of 'check then store' matters.
Sorting puzzle pieces into pairs, you don't hold up each piece against every other (O(n²)). You keep a tray of pieces you've already examined, and as each new piece comes, you glance at the tray for its matching half - an instant check. If the match is there, you've found the pair; if not, you drop the new piece in the tray for a future piece to match against. The tray is your hash map of 'seen' elements, and the glance is the O(1) complement lookup.
Given an array and a value k, determine whether any two elements differ by exactly k. Adapt the complement trick - what do you remember, and what do you look up for each element?
What is the essence of the complement (two-sum) hashing pattern?
Key takeaways
- The complement trick: as you scan, remember seen elements so each element's needed partner is an O(1) lookup.
- It's the unsorted counterpart to two-pointer two-sum: O(n) space instead of requiring sorted input.
- For two-sum, check for the complement before storing the current element to avoid matching it with itself.
- The pattern generalizes to pair-with-difference-k, subarray-sum-k (prefix sums), and longest consecutive sequence.
- Recognize it whenever a brute force pairs each element with another - a remembered set/map removes the inner loop.