← Back to Python Examples

Two Sum

The classic warm-up problem — but the real lesson is seeing how a hash map converts O(n²) to O(n).

Contents

  1. The Problem
  2. Solution 1 — Brute Force O(n²)
  3. The Hash Map Insight
  4. Solution 2 — Hash Map O(n)
  5. Common Variants

1. The Problem

Given a list of integers and a target, return the indices of the two numbers that add up to the target. Exactly one solution exists. You may not use the same element twice.

# nums=[2,7,11,15], target=9  → [0,1]  (2+7=9)
# nums=[3,2,4],     target=6  → [1,2]  (2+4=6)
# nums=[3,3],       target=6  → [0,1]  (3+3=6)

2. Solution 1 — Brute Force O(n²)

Try every pair. If two numbers add to the target, return their indices.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

print(two_sum_brute([2, 7, 11, 15], 9))  # [0, 1]

Correct, but O(n²) — checks every possible pair.

3. The Hash Map Insight

For each number x, we're looking for its complement: target - x. Instead of scanning the rest of the list every time, store what we've already seen in a hash map. Then each lookup is O(1).

# nums = [2, 7, 11, 15], target = 9
#
# See 2:  complement = 9 - 2 = 7.  Is 7 in seen? No.  Store {2: 0}
# See 7:  complement = 9 - 7 = 2.  Is 2 in seen? YES — index 0!
# Return [0, 1]   ✓

4. Solution 2 — Hash Map O(n)

def two_sum(nums, target):
    seen = {}  # value → index

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

print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]
print(two_sum([3, 3], 6))          # [0, 1]
SolutionTimeSpace
Brute forceO(n²)O(1)
Hash mapO(n)O(n)
We check for the complement before storing the current number. This correctly handles the case where the answer uses the same value twice at different indices (e.g., [3,3] with target 6).

5. Common Variants

VariantKey change
Two Sum II (sorted input)Use two pointers from each end instead of a hash map — O(1) space
Three SumFix one element, run two-pointer two sum on the rest
Two Sum — count pairsCount all pairs, not just the first found
Return values not indicesSort, then two pointers — simpler than hash map
The hash-map complement technique generalizes broadly: any time you're searching for a "partner" value in a single pass, ask yourself "can I store what I've seen and look up the partner in O(1)?"