03 two sum

Two Sum

🔗 NeetCode Problem:
https://neetcode.io/problems/two-integer-sum/question?list=neetcode150

🔗 LeetCode Problem:
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

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

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