Two Sum

The question

You are given a list of numbers and a target. Return the positions of the two numbers that add up to the target. There is exactly one answer and you cannot use the same number twice.

Explain it to a ten-year-old

You have a pile of coins and need two that make exactly ten pence. The slow way is to pick up every coin and try it against every other coin. The clever way is to pick up one coin, say a three, and ask “have I already seen a seven?” Keep a note of every coin you put down. Each new coin, you check your note once. One pass through the pile.

If the coins are already lined up smallest to biggest, there is a second clever way. Put one finger on the smallest and one on the biggest. Add them. Too big? The big finger moves left. Too small? The small finger moves right. The fingers walk towards each other and meet in the middle.

Unsorted, hash map. List 3, 8, 1, 6, 5, target 7. Each step: look at one number, ask the note for its partner, then write the number down.

Sorted, two pointers. List 1, 3, 4, 6, 8, target 10. Too small moves the left finger. Too big moves the right one.

The trick

There are two tricks, and which one you use depends on one question: is the list sorted?

Not sorted. Trade space for time. As you walk the list, store each number and its position in a hash map. For each new number, look up target - number. If it is in the map, you are done. One pass, one lookup per element.

Sorted. Trade nothing. Two pointers, one at each end. The sum tells you which pointer to move. Because the list is sorted, moving lo right can only make the sum bigger and moving hi left can only make it smaller, so you never skip the answer.

Sorting an unsorted list first costs n log n, which is slower than the hash map. So the map is the answer to the classic question, and two pointers is the answer to its sorted cousin. Know both and say why.

The steps

Unsorted, hash map:

1. seen = {}.
2. For each index i and value x:
   • need = target - x.
   • If need is in seen, return (seen[need], i).
   • Otherwise seen[x] = i.

def two_sum(a, target):
    seen = {}
    for i, x in enumerate(a):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i

Time O(n). Space O(n).

Sorted, two pointers:

1. lo = 0, hi = len(a) - 1.
2. While lo < hi:
   • s = a[lo] + a[hi].
   • If s == target, return (lo, hi).
   • If s < target, lo += 1. Otherwise hi -= 1.

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1

Time O(n). Space O(1).

The template

Nobody invents this at the whiteboard. Someone worked it out years ago, and the reason it is worth memorising is that it is not a solution to one problem. It is a shape. The shape stays the same and three small pieces change. Learn the shape, understand why each line is there, and a problem you have never seen becomes a problem you have.

The lookup shape, for anything unsorted:

seen = {}                          # STATE: what you remember. Map, or a set if you only need yes/no
for i, x in enumerate(a):
    need = TARGET - x              # KEY: what would complete this element
    if need in seen:
        return seen[need], i       # ON HIT: return, count, or collect and keep going
    seen[x] = i                    # remember this one, after the check, never before

The two-pointer shape, for anything sorted:

lo, hi = 0, len(a) - 1
while lo < hi:
    s = a[lo] + a[hi]              # COMPARE: the thing you measure at the two ends
    if s == TARGET:
        return lo, hi              # ON HIT: return, count, or collect and move both
    if s < TARGET:
        lo += 1                    # too small: the only way up is the left finger
    else:
        hi -= 1                    # too big: the only way down is the right finger

What changes from problem to problem is written in capitals: the state you keep, the key you look up or the thing you compare, and what you do on a hit. Everything else is the same code. Two Sum returns on the first hit. 3Sum fixes one element and runs the sorted shape on the rest, collecting hits. Container With Most Water compares areas instead of sums and moves the shorter wall. The shape did not change.

The part you must understand, not memorise, is why the pointer shape is safe. It works only because the list is sorted, so moving lo cannot make the sum smaller and moving hi cannot make it bigger. If an interviewer changes the problem so that promise is gone, the template is gone with it, and you need to notice.

In GPU infrastructure

Placing a job that needs exactly sixteen GPUs across two partly used hosts is Two Sum over free-GPU counts. Walk the hosts once with a map from free count to hostname and you find the pair in one pass. Sort the hosts by free GPUs and walk from both ends and you have the pointer version, which is how a simple bin packer pairs a big fragment with a small one so the rack does not end up with unusable slivers.

What I am listening for

• Whether you say the brute force first, two loops and n squared, and then improve it. Skipping straight to the map is fine. Not being able to explain what it beats is not.
• Whether you check the map before you insert. Insert first and [3, 3] with target 6 finds itself.
• Whether you ask if the list is sorted. That one question tells me you know there are two tools, not one.
• Whether you can explain why the two-pointer walk never misses the answer. It is the sorted order. If you cannot say that, you have memorised the code.

Where it leads

Two Sum is the first rung on a ladder. Once the two ideas are in your head, these are the same problem in a different costume.

• Two Sum II, sorted input. The two-pointer version, on its own.
• 3Sum. Sort, fix one number, run Two Sum II on the rest. The hard part is skipping duplicates.
• Container With Most Water. Two pointers from the ends, always move the shorter wall. Its own lesson, because the reason to move is the whole point.
• Valid Palindrome. Two pointers from the ends, compare and walk in.
• Remove Duplicates from Sorted Array and Move Zeroes. Two pointers moving the same direction at different speeds.
• Trapping Rain Water. Two pointers from the ends, hard. Do it last.
• Subarray Sum Equals K. The hash map idea again, with running sums instead of single numbers.

Go deeper

• The problem statement: Two Sum on LeetCode. Then Two Sum II for the sorted version.
• Two Pointers overview on Hello Interview covers the pattern, both directions, and the problems that use it.
• Two Sum walked through by NeetCode is eight minutes and the drawing is exactly the one above. The rest of the NeetCode channel has every problem in the list.

With AI on the table. The assistant will hand you the hash map version instantly. I ask it to handle a list with a million numbers where memory is tight and the list is already sorted, and I watch whether you notice the tool should switch tricks. Then I ask what breaks if the same number appears twice.