DSA Pattern: Two Sum & Hashing

The Two Sum problem is the gateway to understanding space-time trade-offs. The goal: find two numbers in an array that sum to a target value.

1. Brute Force - O(N²)

Check every possible pair using two nested loops. Simple but slow for large datasets.

2. Sorting + Two Pointers - O(N log N)

Sort the array first. Use one pointer at the start and one at the end. Move them inward based on the current sum. Limitation: Destroys original indices.

3. Hash Map Optimized - O(N)

Iterate through the array once. For each element x, check if target - x exists in our map. If not, store x in the map.

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

Complexity: Time O(N), Space O(N) because we store elements in the hash map.