Two Sum and Its Variants: The Hash Map Pattern That Shows Up Everywhere

The Two Sum problem is the "Hello World" of hash map problems. Most people solve it, move on, and treat it as a warmup. That's a mistake. The pattern behind Two Sum — trading space for lookup speed — shows up in dozens of harder problems. Understanding it deeply means you can spot it elsewhere.

The Core Insight

You want two numbers that sum to a target. The brute force is obvious: for each element, check every other element. O(n²). The question is: what information would make each check O(1)?

If you know the current number is x, you're looking for target - x. If you've stored every number you've seen so far in a hash map (keyed by value), you can check for target - x in constant time.

That's the whole pattern. Pre-store what you've seen so you can look up what you need.

Problem 1: Two Sum (Easy)

Given an array of integers and a target, return the indices of two numbers that add up to the target. Exactly one solution exists.

Brute Force

// Brute force: O(n²) time, O(1) space
const twoSumBrute = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [];
};

Two nested loops, every pair checked. Works, but times out for large inputs.

Optimized: One-Pass Hash Map

// Hash map: O(n) time, O(n) space
const twoSum = (nums, target) => {
  const seen = new Map(); // value → index
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    
    seen.set(nums[i], i);
  }
 
  return []; // problem guarantees a solution exists
};

One pass through the array. For each element, check if its complement is in the map before adding itself. This way you never match an element with itself.

Problem 2: Two Sum II — Input Array Is Sorted (Medium)

Same problem, but the input is sorted and 1-indexed. Return 1-indexed results. Use O(1) extra space.

The sorted constraint means two pointers beats the hash map here.

// Two pointers: O(n) time, O(1) space
const twoSumSorted = (numbers, target) => {
  let left = 0;
  let right = numbers.length - 1;
 
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    
    if (sum === target) return [left + 1, right + 1]; // 1-indexed
    if (sum < target) left++;   // need larger sum → move left pointer right
    else right--;               // need smaller sum → move right pointer left
  }
 
  return [];
};

When the array is sorted, each comparison lets you discard one end of the window for good: if the sum is too small the smallest element can't be part of any solution, so left++; if too large, the largest can't be, so right--. Either way the window shrinks by exactly one.

Worth being precise here, because "sorted + comparison" makes people reach for the wrong mental model. This is not binary search and it does not halve anything. Counting iterations of the loop on [1..n] with a target that never matches: n=256 → 255 comparisons, n=1024 → 1023, n=4096 → 4095. The window goes 1024 → 1023 → 1022 → …, arithmetic shrinkage, not 1024 → 512 → 256. Binary search on 1024 elements would take 10 comparisons. Two pointers takes up to 1023 — which is fine, because it is O(n) and it only makes one pass, but it is linear, not logarithmic.

Problem 3: 3Sum (Medium)

Find all unique triplets in the array that sum to zero. Return the triplets, not indices. No duplicate triplets.

This is where the pattern compounds. Fix one element, then apply two-pointer two sum on the rest.

Brute Force

// Brute force: O(n³) time, O(n²) space — the result and the `seen` dedup set
// both grow with the number of distinct triplets, which is Θ(n²), not Θ(n)
const threeSumBrute = (nums) => {
  const result = [];
  const seen = new Set();
  nums.sort((a, b) => a - b);
  
  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          const triplet = [nums[i], nums[j], nums[k]].join(',');
          if (!seen.has(triplet)) {
            seen.add(triplet);
            result.push([nums[i], nums[j], nums[k]]);
          }
        }
      }
    }
  }
  return result;
};

Optimized: Sort + Two Pointers

// Sort + two pointers: O(n²) time.
// Space: O(n²) for the result in the worst case — the number of distinct
// zero-sum triplets is itself quadratic. O(1) auxiliary beyond the output,
// plus whatever the engine's sort uses.
const threeSum = (nums) => {
  nums.sort((a, b) => a - b); // NOTE: sorts the caller's array in place
  const result = [];
 
  for (let i = 0; i < nums.length - 2; i++) {
    // Skip duplicates for the fixed element
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // Early exit: smallest possible triplet is positive
    if (nums[i] > 0) break;
 
    let left = i + 1;
    let right = nums.length - 1;
 
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // Skip duplicates for left and right
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
 
  return result;
};

Sorting costs O(n log n) but makes duplicate handling easy — duplicate values are adjacent, so you just skip them with a simple comparison.

Two things about that annotation, because both are easy to state wrongly.

The result is not O(n) space. Array.prototype.sort is in place and the two pointers are O(1), so the only thing that grows is the output — and the output can be quadratic. On [1, -1, 2, -2, …] (distinct values symmetric about zero) the count of distinct zero-sum triplets is close to n²/8: n=400 → 19,800 triplets; n=800 → 79,600; n=1600 → 319,200; n=3200 → 1,278,400. That's a clean 4× per doubling. If you're asked for the space complexity, "O(1) auxiliary, O(n²) output" is the answer; "O(n) for the result" is off by a factor of n.

const caller = [-1, 0, 1, 2, -1, -4];
threeSum(caller);
console.log(caller); // [-4, -1, -1, 0, 1, 2]  ← not what you passed in

Let me trace through [-1, 0, 1, 2, -1, -4]:

After sort: [-4, -1, -1, 0, 1, 2]
 
i=0, nums[i]=-4: left=1, right=5
  sum = -4 + (-1) + 2 = -3 < 0 → left++
  sum = -4 + (-1) + 2 = -3 < 0 → left++
  sum = -4 + 0 + 2 = -2 < 0 → left++
  sum = -4 + 1 + 2 = -1 < 0 → left++
  left >= right, stop.
 
i=1, nums[i]=-1: left=2, right=5
  sum = -1 + (-1) + 2 = 0 → push [-1,-1,2]. Skip dupes. left=3, right=4.
  sum = -1 + 0 + 1 = 0 → push [-1,0,1]. left=4, right=3. Stop.
 
i=2, nums[i]=-1: same as nums[1], skip (duplicate).
 
i=3, nums[i]=0 > 0? No. left=4, right=5
  sum = 0 + 1 + 2 = 3 > 0 → right--. left >= right, stop.
 
Result: [[-1,-1,2], [-1,0,1]]

The Hash Map Pattern Family

Two Sum is the entry point, but the underlying pattern — precompute complements — appears in many forms:

// Count elements: value → count
const countMap = new Map();
for (const num of nums) {
  countMap.set(num, (countMap.get(num) ?? 0) + 1);
}
 
// Index elements: value → index
const indexMap = new Map();
for (let i = 0; i < nums.length; i++) {
  indexMap.set(nums[i], i);
}
 
// Check complement existence: O(1) per lookup
const complement = target - x;
if (map.has(complement)) { /* found */ }

You'll see this in "Four Sum Count" (four arrays, count pairs summing to target), "Subarray Sum Equals K" (prefix sums in a map), and "Longest Consecutive Sequence" (store all numbers, check sequences in O(1)).

Interview Tips

"What if there are multiple solutions?" The problem says exactly one, but if there could be multiple, you'd collect all pairs where the complement was seen. For 3Sum, sorting + two pointers handles deduplication cleanly.

"Can you do it without extra space?" With an unsorted array, no — you can't do better than O(n) space if you want O(n) time. With a sorted array, two pointers gives O(1) space. Know the tradeoff and state it.

The complement check BEFORE insertion. The most common bug is checking after inserting, which lets an element match with itself. Always check seen.has(complement) before seen.set(nums[i], i).

3Sum duplicate skipping. Two places: skip duplicates on the outer loop (if i > 0 && nums[i] === nums[i-1] continue), and skip duplicates after finding a zero-sum triplet on the inner pointers. Missing either causes duplicate output.

What to know for follow-ups: 1. Two Sum, 167. Two Sum II, 15. 3Sum, 18. 4Sum, 560. Subarray Sum Equals K.