DSA Two Sum

The problem

Two Sum asks for two values in a list that add up to a target. The two values sit at different positions. The same element never counts twice.

The answer in this article is the pair of values. A list with no working pair answers None. The cases below include one list where the same value appears twice and may be used twice, once per copy.

cases = [
    ([2, 7, 11, 15], 9, (2, 7)),
    ([3, 5, 2, 8, 4], 10, (2, 8)),
    ([3, 3], 6, (3, 3)),
    ([1, 2, 3], 7, None),
]
for nums, target, expected in cases:
    print("nums", nums, "target", target, "pair:", expected)

Read one row at a time. In the first row, 2 + 7 makes 9. In the third row, the two separate copies of 3 make 6. The last row has no pair at all.

Intuition: try pairs until one fits

The first idea pairs the first value with each later value. Then it pairs the second value with each later value. Some pair, somewhere in that process, either fits or does not.

The idea always works. Its cost is the trap. The pair sits late in a longer list, and the search pays for nearly every wrong pair before reaching it.

nums = [3, 5, 2, 8, 4]
target = 10
checked = 0
answer = None
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        checked += 1
        if nums[i] + nums[j] == target:
            answer = (nums[i], nums[j])
            break
    if answer is not None:
        break
print("pair:", answer[0], answer[1])
print("pairs checked:", checked)

Five values hold ten pairs in total. This search checked eight of them for one answer. Doubling the list roughly quadruples the pair count, and a late pair costs nearly all of them.

Brute force: every pair, counted

The brute force is the intuition, written as a function. Two nested loops generate each pair once. A counter records how many pairs were tested.

Pairs are generated with the second index always ahead of the first. That rule guarantees two things. No element pairs with itself, and no pair is tested twice in swapped order.

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

pair, checked = two_sum_brute([3, 5, 2, 8, 4], 10)
print("pair:", pair)
print("pairs checked:", checked)
pair, checked = two_sum_brute([1, 2, 3], 7)
print("no-pair result:", pair)
print("pairs checked:", checked)

The no-pair row is the expensive one. Only a full sweep proves that no pair works. The brute force pays the full pair count exactly when the answer is bad news.

The optimal solution: store each value, look up its complement

A complement is the partner value that completes the target, and storing each seen value in a map while looking up the current value's complement turns the search into one walk. That one sentence is the whole method.

The complement of a value is target minus the value. A lookup in the map answers whether that complement appeared earlier. A hit ends the search, because the stored complement and the current value form the pair.

def two_sum(nums, target):
    seen = {}
    for num in nums:
        need = target - num
        if need in seen:
            return (need, num)
        seen[num] = True
    return None

cases = [
    ([2, 7, 11, 15], 9, (2, 7)),
    ([3, 5, 2, 8, 4], 10, (2, 8)),
    ([3, 3], 6, (3, 3)),
    ([1, 2, 3], 7, None),
]
for nums, target, expected in cases:
    result = two_sum(nums, target)
    print("nums", nums, "target", target, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The duplicate row works because the first 3 is stored before the second 3 is examined. The lookup happens before the store, and that order matters.

Walkthrough: target 10 in [3, 5, 2, 8, 4]

The walk visits one value at a time. The state is the map of values seen so far. Each step looks up one complement, then stores the current value if the lookup missed.

nums = [3, 5, 2, 8, 4]
target = 10
seen = {}
for num in nums:
    need = target - num
    print("value", num, "- needs", need, "- in map:", need in seen)
    if need in seen:
        print("pair found:", need, "+", num, "=", target)
        break
    seen[num] = True
    print("map now holds:", sorted(seen))

The fourth value, 8, needs 2. The value 2 entered the map one step earlier. The pair is read straight off the state, with no backtracking.

Complexity

The brute force tests up to n times n minus 1, divided by 2, pairs for n values, so its time is O(n^2). The map walk does one lookup and one store per value, so its time is O(n).

The brute force stores only its counters, so its extra space is O(1). The map stores up to one entry per value, so its space is O(n).

for n in [5, 10, 20]:
    pairs = n * (n - 1) // 2
    print("values", n, "- brute pairs:", pairs, " map lookups:", n)

Counts beat clocks here. At 20 values the pair count is 190 against 20 lookups. The map trades memory for that gap.

Edge cases and pitfalls

Using the same element twice is the classic wrong answer. A single 5 does not make 10 by pairing with itself. The map avoids the error naturally, because a value is stored only after its own lookup missed.

Storing before looking up would break that protection. The current value would find itself in the map whenever the target is double the value. Order inside the loop is part of the algorithm.

def two_sum(nums, target):
    seen = {}
    for num in nums:
        need = target - num
        if need in seen:
            return (need, num)
        seen[num] = True
    return None

print("one 5, target 10:", two_sum([5, 1], 10))
print("two 5s, target 10:", two_sum([5, 5], 10))
print("no pair:", two_sum([1, 2, 3], 7))
print("empty list:", two_sum([], 5))
print("negative values:", two_sum([-1, 4, 2], 3))
print("pair at the very end:", two_sum([9, 8, 1, 2], 3))

The negative row works with no special handling. A complement is plain subtraction, and subtraction handles signs on its own.