Two Sum - LeetCode Problem #1

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. You may assume each input would have exactly one solution.

Example:

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

---

Approach 1: Brute Force (O(n²))

Check every pair of numbers.

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

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

---

Approach 2: Hash Map (Optimal - O(n))

Store complements in a Map as you iterate.

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>(); // value -> index
  
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    
    map.set(nums[i], i);
  }
  
  return [];
}

Time: O(n) | Space: O(n)

---

How It Works

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

i=0: num=2, complement=7 → 7 not in map → map={2:0}
i=1: num=7, complement=2 → 2 IS in map! → return [0, 1] ✓

---

Visual Flow

flowchart LR
    A["nums: [2,7,11,15]<br/>target: 9"] --> B["i=0, num=2<br/>complement=7"]
    B --> C{"7 in map?"}
    C -->|No| D["map: {2:0}"]
    D --> E["i=1, num=7<br/>complement=2"]
    E --> F{"2 in map?"}
    F -->|Yes| G["Return [0,1]"]

Loading

---

Key Takeaway

The hash map approach is the classic "trading space for time" optimization. The insight: instead of asking "what complement do I need?" for each element (O(n) per element), store what you've seen so far and check in O(1).