# LeetCode 1: Two Sum

## Problem Restatement

We are given an array of integers called `nums` and an integer called `target`.

We need to find two different positions in the array such that the two numbers at those positions add up to `target`.

Return the two indices.

The same element cannot be used twice. That means if `nums[i]` is used as the first number, we need another index `j`, where `i != j`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` and an integer `target` |
| Output | A list containing two indices |
| Constraint | The two indices must be different |
| Guarantee | There is exactly one valid answer |

Example function shape:

```python
def twoSum(nums: list[int], target: int) -> list[int]:
    ...
```

## Examples

Consider this input:

```python
nums = [2, 7, 11, 15]
target = 9
```

We need two numbers that add up to `9`.

The first number is `2`.

To reach `9`, we need:

```python
9 - 2 = 7
```

The number `7` exists at index `1`.

So the answer is:

```python
[0, 1]
```

Another example:

```python
nums = [3, 2, 4]
target = 6
```

We try to find two numbers that add up to `6`.

`2 + 4 = 6`.

Their indices are `1` and `2`.

So the answer is:

```python
[1, 2]
```

A tricky example:

```python
nums = [3, 3]
target = 6
```

Here, `3 + 3 = 6`.

But we must use two different elements.

The first `3` is at index `0`.

The second `3` is at index `1`.

So the answer is:

```python
[0, 1]
```

## First Thought: Brute Force

The most direct way is to try every possible pair.

For each index `i`, we check every later index `j`.

If:

```python
nums[i] + nums[j] == target
```

then we return:

```python
[i, j]
```

Code:

```python
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        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 works because it checks every valid pair exactly once.

## Problem With Brute Force

The brute force solution checks many pairs.

If the array has `n` numbers, then for each number we may compare it with many other numbers.

The time complexity is:

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

For a small array, this is fine.

For a large array, this becomes slow. We need a way to avoid checking every pair manually.

## Key Insight

For each number, we do not need to search the whole array again.

Suppose the current number is:

```python
x = nums[i]
```

We need another number:

```python
target - x
```

This needed number is called the complement.

For example:

```python
target = 9
x = 2
complement = 9 - 2 = 7
```

So while scanning the array, we can ask:

“Have I already seen the complement?”

To answer this quickly, we use a hash map.

The hash map stores:

```python
number -> index
```

So when we visit a number, we can check in constant time whether its complement appeared before.

## Algorithm

Create an empty hash map called `seen`.

This map will store numbers we have already visited, together with their indices.

Then scan the array from left to right.

For each index `i` and number `num`:

1. Compute the complement:

```python
need = target - num
```

2. Check whether `need` already exists in `seen`.

3. If it exists, return:

```python
[seen[need], i]
```

4. Otherwise, store the current number:

```python
seen[num] = i
```

The order matters.

We check first, then insert.

This prevents using the same element twice.

For example, with:

```python
nums = [3, 3]
target = 6
```

At index `0`, `num = 3`.

We need another `3`, but `seen` is still empty.

So we store:

```python
seen[3] = 0
```

At index `1`, `num = 3`.

We need another `3`.

Now `seen` contains `3`, so we return:

```python
[0, 1]
```

## Correctness

We scan the array from left to right.

At each index `i`, the hash map contains only numbers from earlier indices.

That means every index stored in `seen` is different from `i`.

For the current number `nums[i]`, the only value that can form the target is:

```python
target - nums[i]
```

If this value already exists in `seen`, then there is an earlier index `j` such that:

```python
nums[j] = target - nums[i]
```

Therefore:

```python
nums[j] + nums[i] = target
```

So returning `[j, i]` is correct.

If the complement does not exist yet, we store the current number and continue.

Because the problem guarantees exactly one valid answer, eventually the second number of that valid pair will be reached. At that moment, the first number will already be in `seen`, and the algorithm will return the correct indices.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array once |
| Space | `O(n)` | The hash map may store up to `n` numbers |

Each lookup in the hash map is expected `O(1)`.

So the full algorithm runs in linear time.

## Implementation

```python
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}

        for i, num in enumerate(nums):
            need = target - num

            if need in seen:
                return [seen[need], i]

            seen[num] = i

        return []
```

## Code Explanation

We start with an empty dictionary:

```python
seen = {}
```

This stores numbers we have already passed.

The key is the number.

The value is its index.

```python
for i, num in enumerate(nums):
```

This gives us both the index and the number.

For every number, we compute the missing number:

```python
need = target - num
```

If `need` already exists in `seen`, then we found the pair:

```python
if need in seen:
    return [seen[need], i]
```

The first index is `seen[need]`.

The second index is the current index `i`.

If we do not find the needed number, we store the current number:

```python
seen[num] = i
```

This means future numbers can pair with it.

The final return is only for safety:

```python
return []
```

The problem says there is exactly one answer, so this line should not be reached for valid LeetCode input.

## Testing

We can test the solution with a few important cases.

```python
def run_tests():
    s = Solution()

    assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
    assert s.twoSum([3, 2, 4], 6) == [1, 2]
    assert s.twoSum([3, 3], 6) == [0, 1]
    assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]
    assert s.twoSum([0, 4, 3, 0], 0) == [0, 3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 7, 11, 15]`, target `9` | Basic example |
| `[3, 2, 4]`, target `6` | Pair appears in the middle |
| `[3, 3]`, target `6` | Same value, different indices |
| Negative numbers | Confirms subtraction logic still works |
| Zero values | Checks `0 + 0` with different indices |