> ## Documentation Index
> Fetch the complete documentation index at: https://hanzla.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# 03 two sum

# Two Sum

🔗 **NeetCode Problem**:\
[https://neetcode.io/problems/two-integer-sum/question?list=neetcode150](https://neetcode.io/problems/two-integer-sum/question?list=neetcode150)

🔗 **LeetCode Problem**:\
[https://leetcode.com/problems/two-sum](https://leetcode.com/problems/two-sum)

***

## Problem Statement

Given an array of integers `nums` and an integer `target`, return the **indices** of the two numbers that add up to the target.

You may assume each input has **exactly one solution**, and you **cannot use the same element twice**.

***

## Approach 1: Brute Force (Nested Loop)

### Idea

Check every pair of elements to see if they sum to the target.

### Pseudocode

```
for i from 0 to n-1:
    for j from i+1 to n-1:
        if nums[i] + nums[j] == target:
            return [i, j]
return []
```

### C++ Implementation

```cpp theme={null}
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target)
                    return {i, j};
            }
        }
        return {};
    }
};
```

### Complexity Analysis

* **Time Complexity**: **O(n²)** → Nested loops over the array
* **Space Complexity**: **O(1)** → No extra space needed

### Why it's not optimal?

For large arrays, checking every pair becomes very slow. With 10,000 elements, we'd check \~50 million pairs in the worst case.

***

## Optimized Approach: Using Unordered Map (One Pass)

### Idea

Use a hash map to store elements we've seen along with their indices.\
For each element, calculate what we need (`target - nums[i]`) and check if it exists in the map.\
If it does, we found our pair!

### Key Insight

Instead of checking all future pairs (brute force), we check if the **complement** already exists in previous elements.

### How it works:

1. For each number `nums[i]`, calculate `diff = target - nums[i]`
2. Check if `diff` exists in our hash map
3. If yes, return the indices (previous index and current index)
4. If no, store `nums[i]` with its index for future lookups

### C++ Implementation

```cpp theme={null}
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        
        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            
            if (mp.find(diff) != mp.end())
                return {mp[diff], i};
            
            mp[nums[i]] = i;
        }
        return {};
    }
};
```

### Complexity Analysis

* **Time Complexity**: **O(n)** → Single pass through the array with O(1) average-case lookups
* **Space Complexity**: **O(n)** → Hash map stores up to n elements

### Why it's optimal?

Single pass with O(1) lookups. No redundant checks. Early termination when pair is found. Complement approach is elegant and efficient.

***

## Comparison: Brute Force vs Optimized

| Approach          | Time Complexity | Space Complexity | Pros                  | Cons                       |
| ----------------- | --------------- | ---------------- | --------------------- | -------------------------- |
| **Brute Force**   | O(n²)           | O(1)             | No extra space        | Very slow for large arrays |
| **Unordered Map** | O(n)            | O(n)             | **Fastest**, one pass | Uses extra memory          |

***

## Why Unordered Map is Most Optimal

1. **Single pass**: O(n) time complexity
2. **O(1) lookups**: Average case hash map operations
3. **No redundant checks**: Never checks the same pair twice
4. **Early termination**: Returns immediately when pair is found
5. **Elegant logic**: Complement-based approach is intuitive
6. **Preserves indices**: Returns original array indices correctly

***

## Example Walkthroughs

### Example 1: `nums = [2, 7, 11, 15]`, `target = 9`

**Using Unordered Map:**

```
Initial: mp = {}

i=0: nums[0]=2
  - diff = 9 - 2 = 7
  - 7 not in mp
  - mp[2] = 0 → mp = {2: 0}

i=1: nums[1]=7
  - diff = 9 - 7 = 2
  - 2 IS in mp! ✓
  - Return {mp[2], 1} = {0, 1}
```

Pair found! Indices 0 and 1 (2 + 7 = 9).

### Example 2: `nums = [3, 2, 4]`, `target = 6`

**Using Unordered Map:**

```
Initial: mp = {}

i=0: nums[0]=3
  - diff = 6 - 3 = 3
  - 3 not in mp
  - mp[3] = 0 → mp = {3: 0}

i=1: nums[1]=2
  - diff = 6 - 2 = 4
  - 4 not in mp
  - mp[2] = 1 → mp = {3: 0, 2: 1}

i=2: nums[2]=4
  - diff = 6 - 4 = 2
  - 2 IS in mp! ✓
  - Return {mp[2], 2} = {1, 2}
```

Pair found! Indices 1 and 2 (2 + 4 = 6).

### Example 3: `nums = [3, 3]`, `target = 6`

**Using Unordered Map:**

```
Initial: mp = {}

i=0: nums[0]=3
  - diff = 6 - 3 = 3
  - 3 not in mp (cannot use same element)
  - mp[3] = 0 → mp = {3: 0}

i=1: nums[1]=3
  - diff = 6 - 3 = 3
  - 3 IS in mp! ✓
  - Return {mp[3], 1} = {0, 1}
```

Pair found! Indices 0 and 1 (3 + 3 = 6). Notice we don't use the same element twice because we check before storing.

***

## Key Takeaways

* **Avoid brute force** for this problem (O(n²) is too slow)
* **Unordered map is optimal** (O(n) time, O(1) average lookups)
* **Complement approach**: Calculate what you need (`target - nums[i]`), then look for it
* **Single pass is efficient**: Don't check all future pairs
* **Early termination**: Return as soon as the pair is found
* **Hash map strength**: Fast lookups make finding complements efficient