Two Sum Family

"One element + its complement. HashMap stores what you've seen. O(n) beats O(n²)."

Two Sum spawned a whole family of problems: Three Sum, Four Sum, Two Sum with sorted array, Two Sum with unlimited pairs, subarray sum = k, find pair with given XOR. The core insight: instead of scanning all pairs O(n²), use a HashMap to look up the complement in O(1). Learn every variant.

16 min readdp problems →

Problems you can solve with this pattern

6 problems · click any to start solving

All dp →

1Two Sum II (sorted)MediumSolve

24SumMediumSolve

3Number of Pairs with Sum less than targetMediumSolve

4Max Number of K-Sum PairsMediumSolve

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;
};

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;
};

Medium

Medium

Number of Pairs with Sum less than target

Medium

Solve

Max Number of K-Sum Pairs

Medium

Solve

Check if Pair with Sum Exists in BST

Easy

Solve

Count Good Triplets

Easy

Solve

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 if(i>start && nums[i]===nums[i-1]) continue.

← Advanced Graph: SCC, Bridges & 2-SAT Palindrome Patterns →