🎯 Two Sum

🟢 BeginnerHash Map Pattern

📋 Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Assume exactly one solution exists and you may not use the same element twice.

Example: nums = [2,7,11,15], target = 9 → Output: [0,1] (2 + 7 = 9)

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

function twoSumBrute(array $nums, int $target): array {
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($nums[$i] + $nums[$j] === $target) {
                return [$i, $j];
            }
        }
    }
    return []; // No solution (shouldn't happen per problem)
}
// Time: O(n²), Space: O(1)

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

function twoSum(array $nums, int $target): array {
    $seen = []; // value → index

    foreach ($nums as $i => $num) {
        $complement = $target - $num;

        // Check if we've seen the complement
        if (isset($seen[$complement])) {
            return [$seen[$complement], $i];
        }

        // Store current number's index
        $seen[$num] = $i;
    }
    return [];
}

// Test
$result = twoSum([2, 7, 11, 15], 9);
print_r($result); // [0, 1]

📝 Dry Run

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

Step	i	num	complement	seen map	Action
1	0	2	7	{}→{2:0}	7 not in seen, store 2→0
2	1	7	2	{2:0}	2 found! Return [0,1] ✅

📊 Complexity

Brute Force	O(n²)	O(1)
Hash Map	O(n)	O(n)

🎯 Interview Variations

Three Sum: Find triplets summing to target (sort + two pointer or hash, O(n²))
Two Sum II (Sorted): Use two-pointer technique for O(n) time, O(1) space
Two Sum Count: Count number of pairs (not indices). Use frequency map.
Two Sum BST: Find if two nodes sum to target in BST (inorder + two pointer)

⚠️ Common Mistakes

❌ Returning same element twice - check indices differ
❌ Forgetting to check complement before storing current
❌ Using array_search() which is O(n), making overall O(n²)

All Problems Next: Three Sum