Two Sum: Why the Hash Map Beats Sorting (and When It Doesn't)

Two Sum is usually the first problem anyone solves with a hash map, and the usual lesson is "hash map good, nested loop bad". That is true and incomplete. There is a second respectable answer — sort, then walk two pointers inward — and knowing exactly why the hash map usually wins, and when it does not, is what turns a memorised solution into an explained one.

The problem it solves

Given an array of numbers and a target, return the indexes of two different elements that add up to the target. The input is not sorted. There may be duplicates, negative numbers, or no answer at all.

The brute force checks every pair: n(n - 1)/2 additions, O(n²). Both good answers get rid of that inner loop, but they do it by buying different things.

The intuition

For each value x, the partner you need is fixed: target - x. The question is how to find out whether that partner exists without scanning.

Sorting buys order. In a sorted array, one pointer at each end tells you which way to move: too small a sum means the left value is useless, too large means the right one is. Every step discards one candidate for good — the elimination argument from two pointers. The cost is the sort itself, and the original positions get scrambled.

Hashing buys membership. A hash map answers "have I seen this value?" in constant time on average. So walk the array once and, at each element, ask the map whether its complement has already gone past:

Every pair is discovered exactly once — at the moment its second member arrives and finds the first one waiting in the map.

No order is needed, so no sort, and indexes stay intact because you store them as the map's values.

Watch it run

Watch the map fill as the scan moves right. Each element first asks for its complement, then files itself away. The hit happens on the second half of the pair, never the first.

The code

Both correct answers, plus the most common broken one.

def two_sum_hash(nums, target):
    seen = {}                                  # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:                 # ask first...
            return (seen[target - x], i)
        seen[x] = i                            # ...then remember
    return None

def two_sum_sorted(nums, target):
    order = sorted(range(len(nums)), key=lambda i: nums[i])   # sort indexes
    lo, hi = 0, len(order) - 1
    while lo < hi:
        total = nums[order[lo]] + nums[order[hi]]
        if total == target:
            return tuple(sorted((order[lo], order[hi])))
        if total < target:
            lo += 1
        else:
            hi -= 1
    return None

def two_sum_buggy(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        seen[x] = i                            # remember first...
        if target - x in seen:                 # ...then ask
            return (seen[target - x], i)
    return None

print(two_sum_hash([3, 2, 4], 6))      # (1, 2)
print(two_sum_sorted([3, 2, 4], 6))    # (1, 2)
print(two_sum_buggy([3, 2, 4], 6))     # (0, 0)  3 paired with itself
print(two_sum_hash([3, 3], 6))         # (0, 1)

The sorted version sorts the indexes by value rather than sorting the values. That is the one change that keeps it honest about positions; sort the numbers directly and you can only report values.

The buggy version differs from the correct one by the order of two lines. Storing x before asking lets 3 find itself when the target is 6. Ask first, then remember — and the [3, 3] case still works, because the second 3 finds the first one already in the map.

We checked the two correct versions against each other on thousands of small random arrays with duplicates and negatives: they always agree on whether an answer exists, and every pair they return is two distinct indexes that hit the target.

The complexity

• Hash map: O(n) time on average, O(n) extra space. One pass, one lookup and one insert per element.
• Sort + two pointers: O(n log n) time for the sort, then an O(n) walk. O(n) extra space for the index array.

So on the problem as stated — unsorted input, indexes wanted — the hash map is better on time and equal on space. That is the whole case for it.

When sorting wins

The comparison flips as soon as the problem changes shape, and interviewers like to change it:

• The input is already sorted. Then the two-pointer walk is O(n) time and O(1) space. The hash map is still O(n) time but spends O(n) memory for nothing.
• You need all distinct pairs, or three or four numbers. For 3Sum you sort once, then run the two-pointer walk for every first element: O(n²) total with no extra structure, and duplicates are skipped simply by stepping past equal neighbours. The hash-map version works too but deduplicating triples is messier.
• Values are wanted, not indexes, and memory is tight. Sorting in place needs no auxiliary structure at all.
• Adversarial input. Hash lookups are constant time on average. Crafted keys that collide can degrade them; a sort has a guaranteed bound.

And one case where the hash map wins even harder: a stream. The hash version can answer the moment the second half of a pair arrives, without ever seeing the rest of the input. Sorting needs everything first.

Where it goes wrong

• Remember-then-ask. The self-pairing bug above.
• Sorting the values and returning their new positions. The indexes no longer refer to the caller's array.
• Assuming one answer. The classic statement guarantees exactly one; many variants do not. Say what you return when there is none, and whether you return the first pair found or all of them.
• Overwriting duplicates. seen[x] = i keeps the latest index for a repeated value. For "any valid pair" that is fine; for "the pair with the smallest indexes" it is not.

How to say it in an interview

"Brute force is every pair, O(n²). I can do better two ways. Sorting and then walking two pointers inward is O(n log n), but I would have to sort indexes to keep the original positions. A hash map from value to index gets it in one pass: for each element I check whether target - x is already in the map, and only then store x, so an element cannot pair with itself. That is O(n) time and O(n) space. If the array were already sorted I would switch to two pointers for O(1) space."

Two approaches, a reason to pick one, and the condition that would change your mind — that is the answer being graded.