# Two Sum

[LeetCode #1](https://leetcode.com/problems/two-sum/) · Easy · `array`, `hash map`

> "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.

## 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.

```python
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)$

```python
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)$

```python
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.

```python
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).

---

From https://taosu.blog/notes/0001-two-sum