Two Sum · Data Structures & Algorithms

Two Sum is the problem everyone memorizes and nobody learns, which is backwards, because the six lines of code are disposable and the idea underneath them is not. That idea, trading memory for speed with a hash map, is the single most reused move in array problems. Brute force checks every pair for O(n²), while a hash map turns "find the partner" into one lookup and drops the whole thing to O(n). Learn the swap, not the lines.

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

You may assume each input has exactly one solution, and you may not use the same element twice.

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

Output: [0, 1]

nums[0] + nums[1] = 2 + 7 = 9. We return the indices (0 and 1), not the values.

The Obvious Approach (Brute Force)

The brute-force version checks every pair and returns the first one that sums to the target.

The code uses two nested loops, and the inner one starts at i + 1 rather than 0, so each pair gets tested once instead of twice.

python

def two_sum_brute(nums, target):
    # For every element...
    for i in range(len(nums)):
        # ...check every OTHER element after it
        for j in range(i + 1, len(nums)):
            # Do they add up to target?
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # No solution found

It works, and it's quick to write. But those nested loops hide a cost: for every element, you rescan everything that comes after it.

That's O(n²) time. For 1,000 elements, that's up to 1,000,000 operations; bump the input to 10,000 and you're at 100,000,000. That curve is the reason to keep looking for something better.

The trap: it's tempting to stop at correct. But O(n²) on an array problem is almost always a sign a better approach exists. When you see nested loops checking pairs, ask: "Can I eliminate one of these loops?"

The Key Insight

For each number nums[i], what are we really looking for?

At nums[i] = 2 with target = 9, we need a 7 somewhere in the array. We aren't testing random sums and hoping one lands. We're hunting one specific value, target - nums[i], called the complement.

So the question flips: "have I already seen a 7?" Answering "does this value exist" in O(1) is exactly a hash map's job (a dict, in Python).

The Hash Map Solution

Kill the inner loop by building a hash map as you go, one entry per number, holding its index.

For each number, ask: "Is my complement already in the map?" If yes, that's the pair. If no, add the current number, since some later number might need it as a complement. Watch it run:

Start with Empty Map

We'll store {value: index} as we go. Looking for target = 9.

map = {}

need: 9 - 2 = 7

seen maps each number to its index. Each step checks for the complement, then stores the current number.

python

def two_sum(nums, target):
    seen = {}  # {number: index} — what we've seen so far
    
    for i, num in enumerate(nums):
        complement = target - num       # What partner do we need?
        
        if complement in seen:          # Already seen it?
            return [seen[complement], i]  # Found the pair!
        
        seen[num] = i  # Store for future lookups
    
    return []  # No solution found

The order of those two steps carries more weight than it looks. You check for the complement before storing the current number, and that sequencing is what keeps you from pairing an element with itself. Picture an array holding a single 4 with target = 8. If you stored first, the map would already contain that 4 when you asked for its complement, and you'd happily return [i, i] as if two different fours summed to eight. Checking first means the map only ever holds numbers from earlier positions, so every match you find is a genuinely distinct element.

A single loop with one hash map lookup per element gives us O(n) time, O(n) space.

One pass with a single lookup per element, and the scan that made brute force quadratic is gone.

The tradeoff is memory: the hash map costs O(n) space. In return, time drops from O(n²) to O(n). Past a few dozen elements, that's a deal worth making almost every time.

Why This Matters

Two Sum teaches the optimization reflex you'll reuse most: when you're searching for something over and over, use a hash map to remember what you've seen.

You'll reach for it constantly: finding duplicates, counting occurrences, checking membership, caching work you've already done.

The hash map reflex: Whenever you see O(n²) caused by "for each element, search for something," ask: "Can I use a hash map to make that search O(1)?"

Try It Yourself

This variation returns whether a valid pair exists (True/False) instead of indices. Fill in the two missing pieces.

Try it yourself

Pair Sum Exists

Given an array of integers nums and an integer target, return True if there exist two distinct elements in the array that add up to target, otherwise return False.

You may not use the same element twice (i.e., you can't use nums[i] + nums[i]).

Constraints:
• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

Examples

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

Output: True

2 + 7 = 9, so a valid pair exists

Input: nums = [1, 2, 3, 4], target = 10

Output: False

No two numbers sum to 10

Input: nums = [3, 3], target = 6

Output: True

3 + 3 = 6 (using two different elements)

Pair Sum Exists

Click "Run" to execute your code

Test Cases

Input: [2, 7, 11, 15], 9Expected: True

Input: [1, 2, 3, 4], target = 10Expected: False

Input: [3, 3], 6Expected: True

Input: [5], 10Expected: False

Input: [1, 5, 3, 7, 9], 12Expected: True

Solution

def solution(nums, target):

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2

if nums[mid] == target:

return mid

elif nums[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Time: O(log n) | Space: O(1)

Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

What's Next

Two Sum is O(n) time, O(n) space with a hash map. But what if you couldn't use that extra space?

Next up is Two Sum II, where the array is sorted and you need O(1) space. The hash map is off the table. But the sorted order hands you something better: two pointers.

Hash Map Optimization

Two Sum trains one reflex: spot the brute-force O(n²), then collapse the repeated search into an O(1) hash-map lookup. The "store what you've seen" move comes back constantly. And when the data has structure, like being sorted, there's an even cleaner way in.

Key Takeaways

The most common interview optimization: a hash map for O(1) lookups
When brute force is O(n²) from nested loops, look for ways to eliminate one loop
Trading space for time (hash map) is often the right move
Next up: what happens when you can't use extra space?

Next: Two Sum II - Input Array Is Sorted