Complement Hashing
Walk the array once. For each element ask the map whether the value that completes the requirement has already been seen, then insert the current element.
HashingO(n) time, O(n) spaceNew21 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
find a pair that sums to X
has this value been seen
count pairs with property
The template
Get this into muscle memory, then adapt the condition per problem.
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need)!, i];
seen.set(nums[i], i);
}If you are stuck
The generic hint ladder for this pattern, in order.
- 1Brute force is every pair. What would let you skip the inner loop?
- 2You only need to know whether a specific number appeared earlier.
- 3Store value to index while scanning, and query before inserting.
Drill it
Every problem in the bank that uses this pattern.
0 / 21 solved