Complement / Two Sum

Two Sum

For target T and current number x, check if T−x is in the map. If yes, you found your pair. If no, store x in the map and move on. Works because every pair has two numbers — you'll see the complement eventually.

O(n)

How It Works

Two Sum asks for a pair of numbers adding to a target T. Brute force tests all O(n²) pairs, but the pair relationship is really a lookup: for the current number x, you need to know whether T − x has appeared before. A hash map from value to index answers that in O(1). Walk the array once; for each x, check the map for T − x, and if absent, record x before moving on.

This one-pass scheme finds every pair because whichever element of a pair comes second will find its partner already stored. Time drops to O(n) with O(n) space — the archetypal example of trading memory for a nested loop.

Step-by-Step Visualization

Target = 9. Start with empty hash map

Currentnums[0] = 2

Need9 - 2 = 7

In map?No

Hash Mapempty

1/3

Code

Java

static int[] twoSum(int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<>(); // value → index

  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];

    if (map.containsKey(complement)) {
      return new int[]{map.get(complement), i};
    }

    map.put(nums[i], i); // Store for future lookups
  }

  return new int[]{};
}

// Example: twoSum(new int[]{2, 7, 11, 15}, 9)
// Answer: [0, 1] → 2 + 7 = 9

Tips & Gotchas

1Store values as you go — don't pre-build the hash map

2For each number, check if its complement (target - num) already exists

3This works because if [a, b] is a pair, you'll find b when processing a (or vice versa)

Practice Problems

1Two Sum
2Two Sum II - Input Array Is Sorted
34Sum II
4Pairs of Songs With Total Durations Divisible by 60

About the Complement / Two Sum Pattern

Instead of checking every pair, store each number in a map as you go. For each new number, check if the 'complement' (what you need to reach the target) is already in the map. One pass, O(n).

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

Why insert into the map after checking, not before?

Checking first prevents an element from matching itself when T is exactly twice its value. Inserting after the lookup guarantees any complement found is a genuinely different array position.

When are two pointers better than a hash map for pair sums?

If the array is already sorted, or sorting is acceptable, converging two pointers finds the pair in O(n) with O(1) extra space. The hash map wins when the input is unsorted and original indices must be reported, since sorting would scramble them.

How does this idea extend to 3Sum or 4Sum?

Fix all but two of the numbers with outer loops and solve the remaining pair with the hash map or two pointers, giving O(n²) for 3Sum. For 4Sum II with separate arrays, precompute all pairwise sums of two arrays in a map and look up the negated sums of the other two.