Two Sum

You'll replace a slow search with a hash map lookup of values you've already seen. The same trick solves subarrays summing to k. You need loops, indexes, and dictionaries. Related chapter: hash maps.

1. The problem

You get a list of integers nums and an integer target. Find two different positions whose values add up to target, and return their indexes in either order. Don't change the input. LeetCode 1 promises exactly one answer. Our function also returns [] when there is none, so that case is covered.

"Different positions" is the phrase that matters. Two equal values are fine, as in [3, 3]. Using one index twice is not, as in [5].

2. A correct baseline

Try every pair of positions i < j.

def baseline(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]
    return []

assert baseline([4, 1, 8, 6], 10) == [0, 3]
assert baseline([3, 3], 6) == [0, 1]
assert baseline([5], 10) == []
assert baseline([], 0) == []

When no pair exists, this checks all n(n − 1) / 2 pairs. That's O(n²) time: the work grows with the square of the list's length. With 10,000 numbers, it's about fifty million additions. It uses O(1) extra space, meaning a fixed amount no matter how long the list is.

The bottleneck. Look at what the inner loop is doing. For a given nums[i], only one value can complete the pair: target - nums[i]. So the inner loop searches the list for one value. Every pass of the outer loop searches again through numbers it has already looked at.

3. The observation

Take [4, 1, 8, 6] with target 10. When you reach the 6, you need a 4. You saw a 4 already, at index 0. If you had written it down, you could answer at once instead of searching. Rewrite the condition so each side depends on one position:

nums[i] + nums[j] == target ⟺ nums[i] == target − nums[j]

Walk left to right, and treat each position j as the second number of a pair. Now ask: "Did the value target − nums[j] appear earlier?" A hash map answers that in O(1) time on average, meaning the time doesn't grow with the list. Map each value you've seen to an index where it appeared.

Two details follow. The hash map must hold only earlier positions, so look up the partner before you store the current value. And it needs only one index per value, because any matching partner works.

This works because the condition is an exact match. A hash map answers "is this exact value here?" It can't answer "is some value in this range here?"

4. The solution and a trace

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        """Return distinct matching indexes; return [] if no pair exists."""
        seen = {}  # Each value maps to an index strictly before i.
        for i, number in enumerate(nums):
            needed = target - number
            if needed in seen:
                return [seen[needed], i]
            seen[number] = i
        return []

solve = Solution().twoSum
assert solve([4, 1, 8, 6], 10) == [0, 3]
assert solve([3, 3], 6) == [0, 1]
assert solve([5], 10) == []
assert solve([], 0) == []

Trace [4, 1, 8, 6] with target 10:

We found the pair when its second number arrived. We only had to remember the first one.

5. Why it works

What stays true. At the start of step i, seen holds every value from nums[0 .. i − 1], each mapped to an earlier index where it appears. This is true at the start, when nothing is seen and seen is empty. Each step adds nums[i] only after its lookup, so it stays true.

Every pair it returns is right. At step i, seen[needed] is an index before i, so the two positions differ. Its value is target − nums[i], so the two values sum to target.

It never misses a pair. Suppose a pair exists. Of all such pairs (p, q) with p < q, pick the one whose second index q comes first. If the function hasn't returned by step q, then nums[p] is in seen, so it returns there. So it always finds a pair when one exists, and returns [] only when none does.

When a value repeats, seen[number] gets overwritten. That's safe: you only need some earlier index holding the value, and any one completes the pair.

6. Cost, edge cases, and failure

Cost. One pass, with one lookup and at most one insert per number. That's O(n) time on average: the work grows in step with the list. The hash map takes O(n) extra space. "On average" is the usual hash map caveat, and for Python integers it doesn't matter in practice.

Edge cases. Empty and one-number lists return []. Negative numbers and zero need no special handling, because the rewrite is plain arithmetic. Equal values work because the earlier copy is already in seen when the later one arrives.

Where it fails. If you store before you look up, a value can pair with itself:

class StoreFirst:  # deliberately wrong order, for comparison
    def twoSum(self, nums, target):
        seen = {}
        for i, number in enumerate(nums):
            seen[number] = i
            if target - number in seen:
                return [seen[target - number], i]
        return []

assert StoreFirst().twoSum([5], 10) == [0, 0]  # wrong: position 0 used twice
assert solve([5], 10) == []

The order of lookup and insert matters in subarrays summing to k too, for the same reason.

import random

rng = random.Random(1)
for _ in range(2000):
    nums = [rng.randint(-5, 5) for _ in range(rng.randint(0, 10))]
    target = rng.randint(-10, 10)
    found = solve(nums, target)
    if baseline(nums, target):
        i, j = found
        assert i != j and nums[i] + nums[j] == target, (nums, target)
    else:
        assert found == [], (nums, target)