Two Sum — LeetCode Solution in Python

The problem, in short

You are given a list of integers and a target number. Exactly one pair of positions in that list adds up to the target, and you must return those two positions. You may not reuse the same element twice, and the order of the two indices you return does not matter.

The input is not sorted, and the values can be negative.

How to think about it

The question to ask is not “which two numbers add up to the target?” but “for the number I am standing on, does its partner already exist?” That reframing is the whole problem. If I am looking at nums[i], the partner I need is exactly target - nums[i]. There is nothing to search for and nothing to guess — the partner's value is fully determined.

So the real problem becomes a lookup problem: have I already seen the value target - nums[i], and if so, where? A dictionary answers that in constant time, which is what turns a quadratic solution into a linear one.

The brute-force approach

The direct reading of the problem is to try every pair. For each index i, walk every later index j and check whether the two values sum to the target.

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

This is correct and it is worth writing once, because it makes the inefficiency obvious: the inner loop re-scans values you have already walked past. Every one of those re-scans is work you could have saved by remembering what you saw.

The optimised approach

Walk the list once. At each element, first check whether its partner is already in the dictionary; if it is, you are done. If it is not, record the current value and its index so that a later element can find it.

The order matters. Checking before inserting is what stops an element from pairing with itself: when target is 8 and the current value is 4, the lookup happens while the current 4 is still absent from the dictionary, so it can only match a different earlier 4.

Python solution

def two_sum(nums, target):
    """Return the indices of the two numbers that add up to target."""
    seen = {}                       # value -> index it was found at

    for i, value in enumerate(nums):
        partner = target - value
        if partner in seen:         # check BEFORE inserting
            return [seen[partner], i]
        seen[value] = i

    return []                       # no pair found

Time and space complexity

One pass over n elements, with a dictionary lookup and insert that are both O(1) on average — so O(n) time. The dictionary can hold up to n entries in the worst case, which is where the O(n) space comes from. That is the trade you are making: memory in exchange for not re-scanning.

Example walkthrough

Take nums = [2, 7, 11, 15] with target = 9.

The answer comes out on the second element. Notice that index 0 was never revisited — it was recalled, which is the entire saving over the brute force.

Common mistakes

1. Inserting before checking. Writing seen[value] = i above the if lets an element match itself. With nums = [3, 5] and target = 6 you would wrongly return [0, 0].
2. Returning the values instead of the indices. The problem asks for positions. Returning [2, 7] instead of [0, 1] is the single most common wrong answer.
3. Sorting the list first. Sorting makes a two-pointer approach possible, but it destroys the original indices — which are the thing you were asked for. If you sort, you must carry the original positions along with the values.
4. Assuming the input is positive. Negative numbers and zero are valid. Any logic that skips values because they are “bigger than the target” breaks immediately on negatives.

Related problems

• 3Sum — Fix one number and run a two-pointer scan over the rest.
• Two Sum II (sorted input) — When the list is already sorted, two pointers beat the hash map on space.
• Contains Duplicate — The same “remember what you have seen” pattern, one step simpler.

More write-ups are indexed in Boopathi's LeetCode solutions.