LeetMotion
You have a list of numbers and a target. Find two numbers that add up to it and return their indices — not the numbers themselves. There's always exactly one answer, and you can't use the same number twice.
2 ≤ nums.length ≤ 10⁴-10⁹ ≤ nums[i] ≤ 10⁹-10⁹ ≤ target ≤ 10⁹Say you're looking at the number 3 and the target is 9. You don't need to guess what the other number is — it has to be 6. That's it. So instead of scanning the whole array again to find a 6, what if you just... remembered whether you've seen one already?
That's the whole idea. Walk through the array once. For every number you see, check your notes — "have I passed the complement yet?" If yes, done. If not, write this number down and move on. A hash map is just those notes, but with O(1) lookup instead of flipping through pages.
Your first instinct is probably right: try every pair and see if they add up. Pick nums[i], then check every nums[j] after it. Simple, works, and gets you TLE on anything over a few thousand elements.
nums[i] and scan everything to its right.nums[i] + nums[j] == target, return [i, j].With 10,000 elements you're looking at ~50 million comparisons. LeetCode gives you about 10–100 million operations before it cuts you off. This just barely fails.
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)): # every pair after i
if nums[i] + nums[j] == target:
return [i, j]
return []Same loop, but this time bring a notepad. As you go, write down every number you've seen and where you saw it: { value: index }. Before writing anything down, check if the number you need is already in the notes.
seen = {}.num, figure out what you need: complement = target − num.seen — you're done. Return [seen[complement], i].seen[num] = i. Move on.[3, 3] with target 6 finds itself as its own complement and returns[0, 0]. Wrong answer, subtle bug.def twoSum(nums, target):
seen = {} # value → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) lookup
return [seen[complement], i]
seen[num] = i # store AFTER checking
return []| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Two nested loops — each of n elements paired with every other |
| Hash Map | O(n) | O(n) | Single pass; O(1) amortized lookup. Worst-case O(n) space if no pair found early |
Two Sum looks deceptively specific, but its shape appears constantly in harder problems. The thing to recognize isn't "hash map" — it's the question: have I seen what I need before?
n ≤ 10⁴ — O(n²) is borderline dead. You need O(n) or O(n log n) at worst.Spotify's "Discover Weekly" has to find pairs of songs in your history that together fit a time slot exactly. They're not comparing every pair of 10,000 songs — that'd be 100 million checks per user per week. They store durations in a hash table and for each song ask: doesslot − duration already exist? Same problem, real scale.
This is the sneakiest one. If you add num to the map first, then check, you might match a number against itself. Try [3, 3], target=6 — index 0 finds its own entry at index 0 and returns [0, 0]. Wrong. Check first. Store after.
Easy slip. You find the pair and return [num, complement] instead of[seen[complement], i]. The map has the index — use it. The problem asks for positions, not values.
Sorting + two pointers is a clean pattern for checking whether a pair exists. But the moment you sort, you lose the original positions. You can't return the right indices anymore. Don't sort if the answer is indices.
[3, 3], target = 6 — same value twice, should give [0, 1] not [0, 0].[0, 4, 3, 0], target = 0 — zero as target, answer is [0, 3].[-3, 4, 3, 90], target = 0 — negatives work fine, answer [0, 2].These use the same idea but push it further. Don't skip the Easy ones — Group Anagrams is much easier if Contains Duplicate clicks first.
Discussion
…