Two Sum Problem -
🍪 Understanding the Problem
Let's imagine you're at a fruit stand with your friend:
You see apples priced at $2, $7, $11, and $15
Your friend says: "I have exactly $9 to spend. Which two apples can I buy?"
The correct answer is the $2 and $7 apples (positions 0 and 1 in the list)
🐢 Method 1: The Slow Way (Brute Force)
How a Beginner Might Solve It:
1. Look at the first apple ($2)
2. Compare it with every other apple one by one:
o $2 + $7 = $9? Yes! We found our pair!
o (If no match, move to the next apple)
Why It's Slow:
For 4 apples, you make:
3 comparisons for the first apple
2 comparisons for the second apple
1 comparison for the third apple
Total: 6 comparisons
For 100 apples, you'd need 4,950 comparisons! 😱
Python Code:
def two_sum_slow(prices, money):
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[i] + prices[j] == money:
return [i, j]
return []
# Test
print(two_sum_slow([2, 7, 11, 15], 9)) # Output: [0, 1]
🐇 Method 2: The Smart Way (Using a Dictionary)
How a Smart Shopper Would Do It:
1. Keep a notebook where you write down:
"If I see an apple that costs $X, I need an apple that costs $(9-X)"
2. As you look at each apple:
o First apple ($2): Write down "Looking for $7"
o Second apple ($7): Check notebook - yes! We needed a $7 apple!
Why It's Fast:
You only walk past each apple once
The notebook (dictionary) gives instant answers
Step-by-Step Code:
def two_sum_fast(prices, money):
notebook = {} # This will store {price: position}
for position, price in enumerate(prices):
needed = money - price
# Check if we've seen the needed price before
if needed in notebook:
return [notebook[needed], position]
# If not, write down this price for future reference
notebook[price] = position
return [] # If no pair found
# Test
print(two_sum_fast([2, 7, 11, 15], 9)) # Output: [0, 1]
🔍 Breaking Down the Fast Solution
Let's go through each step with our example [2, 7, 11, 15], target=9:
Current Needed Notebook
Step What Happens
Price Price Contents
1 2 9-2 = 7 {} Store {2:0}
Found 2 in notebook! Return
2 7 9-7 = 2 {2:0}
[0,1]
🤔 Common Questions Answered
Q: Why use a dictionary?
A: Dictionaries let us check if we've seen a price in constant time (O(1)), making the whole
solution O(n).
Q: What if there are duplicate prices?
A: The notebook only keeps the first occurrence, which is exactly what we want for this
problem.
Q: Why not sort first?
A: Sorting changes the positions (indexes), making it harder to get the correct answer.
💡 Key Takeaways
1. Brute Force (Nested Loops):
o Easy to understand
o Gets very slow for large lists
2. Optimal (Dictionary):
o Uses extra memory for the notebook
o Lightning fast even for huge lists
3. Always Ask:
o "Have I seen the needed price before?"
o "If not, remember this price for later"
🎯 Final Answer
python
def two_sum(nums, target):
seen = {}
for index, num in enumerate(nums):
needed = target - num
if needed in seen:
return [seen[needed], index]
seen[num] = index
return []
# Example Usage
print(two_sum([2, 7, 11, 15], 9)) # Output: [0, 1]
