Two Sum

Problem

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists, and you may not use the same element twice. The answer can be in any order.

Example 1

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Example 2

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]

Example 3

Input:  nums = [3, 3], target = 6
Output: [0, 1]

Constraints

• 2 <= len(nums) <= 10^4
• -10^9 <= nums[i] <= 10^9, -10^9 <= target <= 10^9
• Exactly one valid answer exists

Thinking

• Brute force idea: check every pair → $O(n^2)$.
• Key insight: for each x, I need target - x. Remembering the numbers seen so far answers “have I seen it?” in $O(1)$. Because the answer is indices, remember where each number was too: a dict of value → index.
• Edge cases to remember: duplicates like [3, 3], negative numbers, zeros ([0, 4, 0], target 0), the pair being the last two elements.

Solution

Approach A — my solution: hash set + list.index

Store seen values in a set; when the complement is found, look up its position with nums.index.

Complexity: Time $O(n)$ · Space $O(n)$ — the same Big-O as the best answer.

It is correct, including duplicates: the set only holds earlier elements, and nums.index returns the first occurrence, which is always before index. The only cost is that a set throws the position away, so nums.index has to scan the list again (once, at the end) to find it.

def two_sum_mine(nums: list[int], target: int) -> list[int]:
    seen = set()
    for index, num in enumerate(nums):
        if target - num in seen:
            return [nums.index(target - num), index]  # O(n) second scan: the set lost the index
        seen.add(num)
    return []

Approach B — brute force

Complexity: Time $O(n^2)$ · Space $O(1)$

def two_sum_brute(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]
    return []

Approach C — one-pass hash map ✅ best practice

Same idea as Approach A, but store value → index in a dict, so the answer’s index is already there when the complement is found. No second scan.

Complexity: Time $O(n)$ · Space $O(n)$

def two_sum(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
    return []

Scratch / Experiments

Worst case at the max size ($10^4$): the pair is the last two elements, so every approach has to look at everything — and in Approach A, nums.index scans almost the whole list again. Brute force runs only once because it takes seconds.

big = list(range(10_000))
target = big[-1] + big[-2]
%timeit -n 1 -r 1 two_sum_brute(big, target)
%timeit two_sum_mine(big, target)
%timeit two_sum(big, target)

Takeaways

• Pattern: “find a complement” → store what you’ve seen in a hash table. If the answer needs positions, store value → index in a dict, not just values in a set.
• Mistakes I made:
  • Used a set, which forgets where each value was, so I had to search again with nums.index (an extra $O(n)$ scan). Ask “what do I need back at the end?” and store that.
  • It only works because nums.index returns the first match and the set holds only earlier elements — correct, but subtle. The dict version doesn’t need that reasoning.
  • Watch out for inserting x into seen before checking: that matches an element with itself (e.g. [3, 2, 4], target 6).
• Related problems: Contains Duplicate (#217, “seen” with a set), Two Sum II (#167, sorted input → two pointers, $O(1)$ space), 3Sum (#15, sort + two pointers), Two Sum IV (#653, BST).