Editorial: Two Sum - CompileMate

1 Intuition

The problem asks us to find two numbers that add up to a target. A brute force approach would be O(n²) where we check every pair. However, we can optimize this using a hash map to achieve O(n) time complexity. The key insight is: for each number `num`, we need to find if `target - num` exists in the array. Instead of searching linearly, we can store numbers we've seen in a hash map.

2 Approach

1. Create an empty hash map to store values we've seen 2. Iterate through the array: - Calculate the complement: `complement = target - current_num` - Check if complement exists in the hash map - If yes, return the indices - If no, add current number and its index to the hash map 3. If we finish the loop without finding a pair, no solution exists (but problem guarantees one exists)

3 Complexity Analysis

**Time Complexity:** O(n) - single pass through the array **Space Complexity:** O(n) - hash map stores at most n elements This is better than the brute force O(n²) approach.

4 Solution Code

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

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> num_map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (num_map.count(complement)) {
            return {num_map[complement], i};
        }
        num_map[nums[i]] = i;
    }
    return {};
}

5 Code Walkthrough

```python # Find the target pair efficiently current_num = nums[0] # 2 complement = 9 - 2 = 7 # 7 not in map yet, add 2->0 current_num = nums[1] # 7 complement = 9 - 7 = 2 # 2 is in map! Return [map[2], 1] = [0, 1] ```