Two Sum: from O(n²) brute force to a single hash-map pass

Two Sum is the first problem almost everyone solves, and it is quietly a sales pitch for the hash map. The brute force is two lines of nested loops and it works. The interesting part is the single idea that turns those nested loops into one pass — because that same idea shows up in a dozen harder problems.

The problem

Given an array nums and a target, return the indices of the two numbers that add up to target. Exactly one answer exists, and you can't reuse an element. The constraint that shapes everything: the array can hold up to 10⁴ numbers, and the follow-up asks outright for something better than O(n²).

That follow-up is the whole exercise. The brute force is allowed to exist; the point is to get past it.

Brute force, and why I'd still write it first

Check every pair. If a pair sums to the target, return their indices.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

O(n²) time, O(1) space. On a 10⁴ array that's a hundred million comparisons in the worst case — slow, but not catastrophic, which is exactly why it's a trap: it passes small tests and lulls you. I still write it first in an interview, out loud, because it states the problem precisely and gives me something correct to optimise from. Skipping straight to the clever answer skips the reasoning the interviewer actually wants to hear.

The one trick: turn the question around

The nested loop asks, for every i, "is there a later j that completes the pair?" That re-scans the array n times. Flip the question: as I walk the array once, for the current number x, I am really asking "have I already seen target - x?" That value has a name — the complement — and "have I seen it" is exactly what a hash map answers in O(1).

So I keep a map of value → index for everything I've passed. At each step I look up the complement before inserting the current number. If it's there, I'm done.

One pass, one map

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}                       # value -> index
        for i, x in enumerate(nums):
            if target - x in seen:
                return [seen[target - x], i]
            seen[x] = i

The same shape in C#:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var seen = new Dictionary<int, int>();   // value -> index
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (seen.TryGetValue(complement, out int j)) {
                return new[] { j, i };
            }
            seen[nums[i]] = i;
        }
        return Array.Empty<int>();
    }
}

O(n) time, O(n) space. The order matters: look up the complement before inserting the current value, or an element can match itself when target is exactly 2 * x. This is the version I ship.

Why not just sort and use two pointers?

Sorting plus two pointers also gets you O(n log n) and O(1) extra space, and for the sorted variant (Two Sum II) it's the right call. Here it isn't, for one blunt reason: sorting destroys the original indices, and the problem asks for indices, not values. You'd have to carry each number's original position through the sort and hand it back — more code, more room for bugs, and slower than the hash map's O(n). When the answer is "positions in the input", a value → index map almost always wins.

The pattern worth keeping

Two Sum is not worth memorising. The reusable move is: instead of searching for a pair, store what you've seen and ask whether the thing that completes the current element is already there. A seen map turns "find a matching partner" from an O(n) inner scan into an O(1) lookup.

You meet the same move constantly:

• Contains Duplicate (217) — the degenerate case: the complement is the number itself.
• Two Sum II — sorted input (167) — sorted, so drop the map and use two pointers instead.
• 3Sum (15) — fix one number, then it's Two Sum on the rest.
• Subarray Sum Equals K (560) — same trick on prefix sums: "have I seen prefix - k?"

If you take one habit from this problem, make it the reflex to reach for a seen map the moment you catch yourself writing a second loop just to find a matching value. Two Sum is the cheapest place to learn that the right data structure erases an entire loop.