Pattern Reference
Two Sum Family
"HashMap-based pair/triple sum lookups. Two Sum, Three Sum, Four Sum, best time to buy/sell."
Loading...
Deep Dive Tutorial
Two Sum is the gateway problem to the "complement lookup" pattern. For any "find pair with property P" problem: iterate through elements, and for each element check if its complement (the other element needed to satisfy P) has been seen before. Store what you've seen in a HashMap or Set. This reduces O(n²) to O(n).
| Variant | Approach | Complexity |
|---|---|---|
| Two Sum (indices) | HashMap: value → index | O(n) |
| Two Sum sorted array | Two pointers from both ends | O(n) |
| Two Sum pairs count (allow reuse) | HashMap freq, query before insert | O(n) |
| Three Sum | Sort + fix one + two pointers | O(n²) |
| Four Sum | Sort + fix two + two pointers | O(n³) |
| Subarray sum = k | Prefix sum + HashMap | O(n) |
| Pair with XOR = target | HashMap: value → count | O(n) |
| Count pairs with difference = k | Sort + binary search or HashMap | O(n log n) |
The Core Insight
Two Sum and all key variants
// ===== CLASSIC TWO SUM =====
// For each nums[i], check if (target - nums[i]) was seen before
var twoSum = function(nums, target) {
const map = new Map(); // value → index
for (let i = 0; i < nums.length; i++) {
const comp = target - nums[i];
if (map.has(comp)) return [map.get(comp), i];
map.set(nums[i], i);
}
};
// ===== COUNT PAIRS with sum = target (each element used once) =====
function countPairs(nums, target) {
const freq = new Map();
let count = 0;
for (const n of nums) {
count += freq.get(target - n) ?? 0; // query BEFORE insert
freq.set(n, (freq.get(n) ?? 0) + 1);
}
return count;
}
// ===== SORTED ARRAY: two pointers =====
function twoSumSorted(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const s = arr[lo] + arr[hi];
if (s === target) return [lo, hi];
if (s < target) lo++;
else hi--;
}
return [-1, -1];
}
// ===== THREE SUM: O(n²) =====
// Sort, fix nums[i], two pointers on rest
var threeSum = function(nums) {
nums.sort((a,b)=>a-b);
const res=[];
for(let i=0;i<nums.length-2;i++){
if(i>0&&nums[i]===nums[i-1]) continue; // skip dups for i
let lo=i+1, hi=nums.length-1;
while(lo<hi){
const s=nums[i]+nums[lo]+nums[hi];
if(s===0){
res.push([nums[i],nums[lo],nums[hi]]);
while(lo<hi&&nums[lo]===nums[lo+1]) lo++;
while(lo<hi&&nums[hi]===nums[hi-1]) hi--;
lo++;hi--;
} else if(s<0) lo++; else hi--;
}
}
return res;
};Worked Problems
brain
Two Sum family decision guide:
- Unsorted, find indices → HashMap (value → index)
- Sorted, find pair → Two pointers
- Count all valid pairs (can reuse) → HashMap freq, query before insert
- 3Sum → sort + fix i + two pointers (O(n²))
- 4Sum → sort + fix i,j + two pointers (O(n³))
- Count pairs in range → sort + two pointers, add range at once
- Subarray sum = k → prefix sum + HashMap
Deduplication in kSum: sort first, then skip duplicate values at each recursion level with
- Unsorted, find indices → HashMap (value → index)
- Sorted, find pair → Two pointers
- Count all valid pairs (can reuse) → HashMap freq, query before insert
- 3Sum → sort + fix i + two pointers (O(n²))
- 4Sum → sort + fix i,j + two pointers (O(n³))
- Count pairs in range → sort + two pointers, add range at once
- Subarray sum = k → prefix sum + HashMap
Deduplication in kSum: sort first, then skip duplicate values at each recursion level with
if(i>start && nums[i]===nums[i-1]) continue.