# LeetCode 170: Two Sum III - Data Structure Design

## Problem Restatement

We need to design a data structure that supports two operations:

```python
add(number)
find(value)
```

The operations behave like this:

| Operation | Meaning |
|---|---|
| `add(number)` | Add the number into the internal data structure |
| `find(value)` | Return `True` if any pair of numbers sums to `value` |

The same number may be added multiple times.

The pair must use two different occurrences unless the number appears at least twice.

For example:

```python
add(1)
add(3)
add(5)
```

Then:

```python
find(4) -> True
```

because:

```python
1 + 3 = 4
```

But:

```python
find(7) -> False
```

because no pair sums to `7`.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `add` | Integer `number` | None |
| `find` | Integer `value` | Boolean |

Example class shape:

```python
class TwoSum:

    def add(self, number: int) -> None:
        ...

    def find(self, value: int) -> bool:
        ...
```

## Examples

Example sequence:

```python
twoSum = TwoSum()

twoSum.add(1)
twoSum.add(3)
twoSum.add(5)
```

Now:

```python
twoSum.find(4)
```

returns:

```python
True
```

because:

```python
1 + 3 = 4
```

Next:

```python
twoSum.find(7)
```

returns:

```python
False
```

because no valid pair exists.

Another example:

```python
twoSum.add(3)
twoSum.add(3)
```

Then:

```python
twoSum.find(6)
```

returns:

```python
True
```

because two occurrences of `3` exist.

## First Thought: Store All Numbers in a List

A direct solution is:

| Operation | Idea |
|---|---|
| `add` | Append to a list |
| `find` | Try every pair |

```python
class TwoSum:

    def __init__(self):
        self.nums = []

    def add(self, number: int) -> None:
        self.nums.append(number)

    def find(self, value: int) -> bool:
        n = len(self.nums)

        for i in range(n):
            for j in range(i + 1, n):
                if self.nums[i] + self.nums[j] == value:
                    return True

        return False
```

This works, but `find` takes:

```python
O(n^2)
```

which is too slow.

We can do better with hashing.

## Key Insight

Use a frequency map.

Store:

```python
number -> count
```

Then for each number `x`, the required partner is:

```python
y = value - x
```

There are two cases.

| Case | Condition |
|---|---|
| Different numbers | `x != y` and `y` exists |
| Same number twice | `x == y` and count of `x` is at least `2` |

This lets us answer `find` in linear time.

## Algorithm

Use a hash map:

```python
self.count
```

For `add(number)`:

1. Increment its frequency.

For `find(value)`:

1. Loop through all stored numbers `x`.
2. Compute:

```python
y = value - x
```

3. If `x != y`, return `True` when `y` exists.
4. If `x == y`, return `True` only when the count is at least `2`.

If no valid pair exists, return `False`.

## Walkthrough

Start:

```python
add(1)
add(3)
add(5)
```

Frequency map:

```python
{
    1: 1,
    3: 1,
    5: 1
}
```

Call:

```python
find(4)
```

Check `x = 1`:

```python
y = 4 - 1 = 3
```

Since `3` exists, return:

```python
True
```

Now check:

```python
find(7)
```

Check:

| `x` | `y = 7 - x` | Exists? |
|---:|---:|---|
| `1` | `6` | No |
| `3` | `4` | No |
| `5` | `2` | No |

Return:

```python
False
```

## Correctness

The frequency map stores exactly how many times each number has been added.

During `find(value)`, for every stored number `x`, the algorithm checks whether the complementary value:

```python
y = value - x
```

exists.

If `x != y`, then one occurrence of `x` and one occurrence of `y` form a valid pair whose sum is `value`.

If `x == y`, then the pair uses the same value twice, so at least two occurrences are required. The algorithm checks this using the stored count.

If the algorithm returns `True`, a valid pair exists by construction.

If the algorithm finishes without returning `True`, then no stored number has a valid complementary partner, so no valid pair exists.

Therefore, the algorithm returns the correct result for every `find` call.

## Complexity

Let `n` be the number of distinct stored values.

| Operation | Time | Space |
|---|---|---|
| `add` | `O(1)` average | |
| `find` | `O(n)` | |
| Total storage | | `O(n)` |

Hash table operations are average-case constant time.

## Implementation

```python
class TwoSum:

    def __init__(self):
        self.count = {}

    def add(self, number: int) -> None:
        self.count[number] = self.count.get(number, 0) + 1

    def find(self, value: int) -> bool:
        for x in self.count:
            y = value - x

            if x != y:
                if y in self.count:
                    return True
            else:
                if self.count[x] >= 2:
                    return True

        return False
```

## Code Explanation

The constructor creates the frequency map:

```python
self.count = {}
```

The `add` operation increments the count:

```python
self.count[number] = self.count.get(number, 0) + 1
```

Inside `find`, loop through every stored value:

```python
for x in self.count:
```

Compute the needed partner:

```python
y = value - x
```

If the two numbers are different:

```python
if x != y:
```

we only need the partner to exist:

```python
if y in self.count:
    return True
```

If the numbers are the same:

```python
else:
```

we need at least two copies:

```python
if self.count[x] >= 2:
    return True
```

If no valid pair is found:

```python
return False
```

## Alternative Design: Fast find

We can also optimize for fast `find`.

Idea:

| Operation | Complexity |
|---|---|
| `add` | `O(n)` |
| `find` | `O(1)` |

Store every possible pair sum in a set.

When adding a new number, combine it with all previous numbers and store the sums.

Then `find(value)` becomes:

```python
value in sums
```

This is useful when `find` is called much more often than `add`.

## Testing

```python
def run_tests():
    ts = TwoSum()

    ts.add(1)
    ts.add(3)
    ts.add(5)

    assert ts.find(4) is True
    assert ts.find(7) is False

    ts = TwoSum()

    ts.add(3)
    ts.add(3)

    assert ts.find(6) is True
    assert ts.find(7) is False

    ts = TwoSum()

    ts.add(-1)
    ts.add(1)

    assert ts.find(0) is True

    ts = TwoSum()

    ts.add(0)
    ts.add(0)

    assert ts.find(0) is True

    ts = TwoSum()

    ts.add(2)
    ts.add(4)
    ts.add(6)

    assert ts.find(8) is True
    assert ts.find(5) is False

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `1, 3, 5`, find `4` | Standard example |
| `1, 3, 5`, find `7` | No valid pair |
| Two copies of `3` | Same value used twice |
| Negative and positive values | Mixed signs |
| Two zeros | Duplicate zero case |
| Multiple values | General behavior |