Two Sum

Problem Statement

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

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Constraints:

• Each input has exactly one solution
• You may not use the same element twice

---

Approach 1: Brute Force

Check every pair of numbers.

def twoSum(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 []

Complexity:

• Time: O(n²)
• Space: O(1)

When to use: Only when space is extremely constrained.

---

Approach 2: Hash Map (Optimal)

Use a hash map to store seen numbers and their indices.

def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []

Complexity:

• Time: O(n)
• Space: O(n)

Why it works:

• For each number, we check if its complement exists
• Single pass through the array
• Hash map provides O(1) lookup

---

Approach 3: Two Pointers (Sorted Array)

If the array is sorted or we can sort it:

def twoSum(nums: list[int], target: int) -> list[int]:
    # Create (value, original_index) pairs
    indexed = [(num, i) for i, num in enumerate(nums)]
    indexed.sort()  # Sort by value
    
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        
        if current_sum == target:
            return [indexed[left][1], indexed[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

Complexity:

• Time: O(n log n) due to sorting
• Space: O(n) for indexed array

When to use: When array is already sorted or multiple queries.

---

Comparison

Approach	Time	Space	Best For
Brute Force	O(n²)	O(1)	Tiny arrays
Hash Map	O(n)	O(n)	General case
Two Pointers	O(n log n)	O(n)	Sorted arrays

---

Common Mistakes

1. Using same element twice:

   # WRONG
   if num * 2 == target:
       return [i, i]  # Same index!
   

2. Forgetting to return original indices after sorting

3. Not handling negative numbers (they work fine with all approaches)

---

Follow-up Questions

1. What if there are multiple solutions? Return all pairs using hash map approach.

2. What if numbers can repeat? Store list of indices in hash map.

3. Three Sum? Fix one number, run Two Sum on rest. O(n²).

---

Key Takeaways

• Hash map is the go-to for sum problems
• Think “complement” - what do I need to find?
• Two pointers work great on sorted arrays
• Always clarify: duplicates? multiple solutions? sorted?