Two Sum, From Brute Force to O(n)

The Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.

Brute Force

Check every pair:

def two_sum(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]

This is O(n²) time. Fine for tiny inputs, too slow when n grows.

The Hash Map Insight

For each number x, its partner is target - x. Instead of searching for that partner, remember every number we've seen in a hash map. Then each lookup is O(1).

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

• Time: O(n), one pass.
• Space: O(n), the hash map.

Why It Works

We only ever look backwards at numbers already stored, so we never reuse the same element. The first time a complement matches, we've found our pair.

Kernel Queen tip: Almost every "find a pair/triple that sums to X" problem starts with this hash-map move. Master it here and 3Sum becomes easy.