Two Sum is the first problem everyone solves and the last problem anyone can actually defend. The single-pass hash map answer takes thirty seconds to recite:
def two_sum(nums, target):
seen = {}
for i, n in enumerate(nums):
c = target - n
if c in seen:
return [seen[c], i]
seen[n] = i
return []“O(n) time, O(n) space.” Correct — and also the exact point where a good interviewer starts digging, because that O(n) is hiding a word you didn’t say: amortized.
What “amortized O(1)” commits you to
A hash map lookup is O(1) on average, assuming a hash function that spreads keys uniformly across buckets. Say the bolded part out loud. If every key lands in the same bucket — an adversarial input, or a genuinely bad hash function — each lookup degrades to a linear scan of that bucket. The single pass becomes O(n) lookups × O(n) per lookup: O(n²) worst case.
This is not pedantry. It’s the difference between knowing the answer and knowing the data structure:
- Python dicts and Java HashMaps mitigate this differently — Java 8+ converts long collision chains into red-black trees, capping the worst case at O(n log n).
- Languages with hash-flooding protections (SipHash keyed by a random seed) make adversarial collisions impractical rather than impossible.
- If the interviewer asks for a guaranteed bound, the honest trade is a balanced BST for O(n log n) worst case, or sorting + two pointers for O(n log n) with O(1) extra space.
The follow-up that separates candidates
“The array is read-only and you can’t allocate extra memory.” Now the hash map is off the table. Sorting in place is off the table too — the array is read-only, and you need original indices anyway. What’s left is the O(n²) brute force… unless the array is already sorted, which is exactly why Two Sum II exists as a separate problem: two pointers, O(n) time, O(1) space, no map at all.
The lesson worth retaining: the hash map buys speed with memory and with an assumption about your hash function. Being able to name that assumption — and price out the alternatives when it’s taken away — is what “knowing Two Sum” actually means.
Coach’s note · Next review, skip straight to the worst case: state what breaks the O(1) lookup and what you’d reach for if the interviewer bans the map. The code is the easy 20%.