Two-Sum and Complement Problems
What you'll learn: How to use hash tables to find pairs of numbers that sum to a target value in linear time.
The Core Idea
The "Two-Sum" problem asks: given an array of numbers and a target sum, find two numbers that add up to that target. The naive approach checks every possible pair, taking O(n²) time. Hash tables let you solve this in just O(n) time by storing complements as you go.
How It Works
The key insight is recognizing that for each number x you examine, you're really looking for its complement: target - x. Instead of searching the entire array each time, you use a hash table to remember numbers you've already seen.
The algorithm:
- Create an empty hash table
- For each number in the array:
- Calculate its complement:
complement = target - current_number - Check if the complement exists in the hash table
- If yes: you've found your pair!
- If no: add the current number to the hash table and continue
- Calculate its complement:
Why This Works
Think of it like a guest list at a party. You're pairing people for a dance competition where partners' heights must sum to exactly 12 feet. As each guest arrives, you check your list: "Is there someone here who's the perfect height to pair with this person?" If not, you write down the new guest's height and wait. With a hash table, this "check the list" operation is O(1), making the whole process O(n).
This technique extends beyond Two-Sum: anytime you need to find elements with a specific relationship (sum, difference, etc.), consider whether storing complements in a hash table can eliminate nested loops.
Key Takeaway: Hash tables transform complement-finding problems from O(n²) brute-force searches into O(n) single-pass solutions by trading space for time—storing seen values for instant lookup.