Complement Lookup (Two Sum)

Given an array of integers and a target value, find two numbers that add up to the target and return their indices. This is LeetCode 1, "Two Sum," the problem that has probably been solved more times than any other in interview prep history. It is also the cleanest introduction to a technique that appears everywhere: complement lookup with a hash map.

Why brute force is $O(n^2)$ and unnecessary

The naive approach is straightforward: for each element, scan every other element to see if the two add up to the target. Two nested loops, $O(n^2)$ time. It works, but it is doing far more work than necessary.

The key question to ask is: when you are looking at a number num, what exactly are you searching for? You are not searching for "some number that pairs well." You are searching for one specific value: target - num. That difference is called the complement. If you had a way to instantly check whether the complement exists in the array (and where it is), you could solve the problem in a single pass.

The complement insight

This is the core idea behind complement lookup: reframe "find a pair that sums to target" as "for each element, check whether its complement has already been seen." A hash map gives you $O(1)$ average-time lookups, which is exactly what you need.

The algorithm works as follows. Walk through the array from left to right. For each element num at index i, compute complement = target - num. Check if complement is already a key in your hash map. If it is, you have found your pair: return the stored index and i. If it is not, store num -> i in the hash map and move on.

Walked example: nums = [2, 7, 11, 15], target = 9

Let's trace through this step by step.

Index 0, num = 2: complement = 9 - 2 = 7. The hash map is empty, so 7 is not found. Store {2: 0}.

Index 1, num = 7: complement = 9 - 7 = 2. Check the hash map: 2 is there, mapped to index 0. Return [0, 1]. Done.

We never even looked at 11 or 15. The algorithm found the answer on the second element because the complement was already stored from the first pass.

One-pass vs two-pass

You might wonder: should you first build the entire hash map and then search for complements in a second pass? You can, but it is unnecessary. The one-pass approach, checking before inserting, is sufficient and slightly more elegant. Here is why: if a valid pair (i, j) exists with i < j, then when you reach index j, the element at index i has already been inserted into the map. You will find it.

The one-pass approach also naturally handles a subtle edge case: you never match an element with itself. Because you check for the complement before inserting the current element, the current element is not in the map yet when you search.

Code for Two Sum

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

This runs in $O(n)$ time and $O(n)$ space. Every element is visited at most once, and each hash map operation is $O(1)$ on average.

Handling duplicates and edge cases

What if the array contains duplicate values? For instance, nums = [3, 3] with target = 6. The one-pass approach handles this correctly. When you reach the second 3 at index 1, you compute complement = 3 and find it in the map at index 0. You return [0, 1] before overwriting the map entry.

What if no valid pair exists? The function returns an empty list (or you could raise an exception, depending on the problem's guarantee). In LeetCode's version of Two Sum, the problem guarantees exactly one solution, so you do not need to worry about the no-solution case.

What about negative numbers or zeros? The algorithm does not care: subtraction and hash map lookup work the same regardless of sign.

Extending to 3Sum

LeetCode 15, "3Sum," asks you to find all unique triplets that sum to zero. The key insight is that 3Sum reduces to repeated Two Sum calls. Fix one element nums[i], and then find two elements in the rest of the array that sum to -nums[i]. That inner problem is exactly Two Sum.

In practice, the most efficient 3Sum approach sorts the array first and uses two pointers for the inner search rather than a hash map. After sorting, fix the first element and place a left pointer just after it and a right pointer at the end. If the three-element sum is too small, move the left pointer right; if too large, move the right pointer left. Skip duplicates at each pointer to avoid duplicate triplets.

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    return result

Sorting costs $O(n \log n)$, and the two-pointer scan for each fixed element is $O(n)$, so the overall time is $O(n^2)$. This is optimal for 3Sum: you cannot do better in the general case.

4Sum and beyond

LeetCode 18, "4Sum," generalizes the pattern further. Fix two elements with nested loops and run two pointers on the remaining subarray. The time complexity is $O(n^3)$. In general, k-Sum can be solved in $O(n^{k-1})$ by fixing k-2 elements and running two pointers.

The recursive structure is worth noting: k-Sum reduces to (k-1)-Sum by fixing one element, all the way down to 2Sum as the base case.

Hash map complement lookup vs sorted two pointers

When should you use each approach? Hash map complement lookup is the right choice when the array is unsorted and you need to preserve original indices (as in Two Sum, which asks for indices). It runs in $O(n)$ time and $O(n)$ space.

Sorted two pointers is better when you need to enumerate all pairs or triplets and the output does not require original indices (as in 3Sum, which asks for values). Sorting also makes duplicate-skipping straightforward: just compare adjacent elements.

If the input is already sorted, two pointers gives you $O(n)$ time with $O(1)$ space, which is strictly better than a hash map.

Complexity analysis

For the basic Two Sum with hash map complement lookup: $O(n)$ time, $O(n)$ space. For 3Sum with sorting and two pointers: $O(n^2)$ time, $O(1)$ extra space (ignoring the output). For 4Sum: $O(n^3)$ time. In each case, the complement lookup idea, whether via hash map or two pointers, is what transforms an exponentially worse brute force into something manageable.

The complement lookup pattern is not limited to sum problems. Any time you are searching for a partner element that satisfies a specific relationship with the current element, ask yourself: can I compute what that partner must be and look it up in $O(1)$? If so, you have a complement lookup problem.

Recognizing this pattern

You're probably looking at complement lookup when:

• The problem says "find a pair / two indices / two elements" that satisfy some arithmetic relation (sum, difference, product) with a fixed target.
• You need to return original indices, which rules out sort-then-two-pointer.
• Values can be negative or arbitrarily large, so bucketing or counting-sort tricks do not apply.
• A brute-force "for each i, scan for the partner of nums[i]" loop is the obvious $O(n^2)$ baseline.
• For each element, you can compute exactly what the partner must be (target - num, num + k, num XOR k, etc.) rather than searching by predicate.

Common templates:

• Two-sum complement: for each num, look up target - num in a seen-map keyed by value. Example: Two Sum.
• Pair with fixed difference: for each num, look up num + k or num - k. Example: K-diff Pairs in an Array.
• k-Sum reduction: fix k - 2 elements with nested loops, then solve the inner two-sum with complement lookup or sorted two pointers. Example: 4Sum.
• Pair count with multiplicity: for each num, add the count of complements already seen rather than returning on first hit. Example: Two Sum Less Than K or Count Good Meals.
• XOR complement: for each num, look up num XOR target because XOR is its own inverse. Example: Count Pairs With XOR in a Range.