Two Sum: find indices of two numbers adding to target. Optimal approach?
Options
- Two nested loops over the array, O(n²)
- Sort first, then binary search for each value, O(n log n)
- One pass with a hash map from value to index, O(n) (Correct option)
- Recursion that tries every pair of numbers
Answer
One pass with a hash map from value to index, O(n) time, O(n) space
Why
For each number x, the partner we need is target - x. Instead of searching the whole list for it (O(n) each time), we keep a dict of numbers already seen and their index.
Check the dict (O(1)); if the partner is there, done; otherwise store x. One pass: O(n).
This trade of memory for speed with a hash map is one of the most common interview tricks.
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = iRemember
Need 'have I seen X before?' fast → hash map.