EasyPython

Two Sum

Given a list nums and a target, return indices of two numbers that add up to target. Assume exactly one solution.

Example: nums=[2,7,11,15], target=9 → [0,1]

Two Sum is probably the most-asked coding question there is, and for a reason. Almost everyone can solve it the slow way. What the interviewer is really waiting for is whether you notice the slow way is slow, and what you do about it.

Rules to keep in mind:

You can't use the same element twice. With nums=[3, 2, 4], target=6 the answer is [1, 2], not [0, 0].
Return the indices, not the numbers.
Negative numbers and zeros are allowed: nums=[-3, 4, 3, 90], target=0 → [0, 2].

Start by saying the brute-force version out loud (check every pair), give its cost, then improve it. That's usually how the conversation is expected to go.

Starter code

def two_sum(nums, target):
    pass

💡 Hint 1

Store seen numbers in a dict

💡 Hint 2

For each number check if target - n was seen

✅ Show solution

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

Time O(n), space O(n).

How it works

The slow approach checks every pair with two loops. That's O(n²). For 10,000 numbers it's around 50 million comparisons.

The dictionary version walks the list once. For each number n, it asks "have I already seen the number that would pair with this one?", which is target - n. Dictionary lookups are effectively instant, so the whole thing is O(n).

Walk through nums=[2, 7, 11, 15], target=9:

i	n	need (9 − n)	seen before?	seen after
0	2	7	no	{2: 0}
1	7	2	yes, at 0	return [0, 1]

Why store after checking

Notice the code checks first and adds n to seen afterwards. If you added it first, then nums=[3, 2, 4], target=6 would return [0, 0], pairing the 3 with itself. Checking first makes "can't use the same element twice" automatic, and nums=[3, 3], target=6 still correctly gives [0, 1].

Complexity: O(n) time, O(n) extra space. That's the trade: memory for speed.

Tip: run your code in a local Python environment, Jupyter or Google Colab.