When does a hash map beat a nested loop?
Name the time and space tradeoff, then say when the nested loop is still the right answer.
Points worth saying
- A nested scan of two lists is quadratic. A hash map lookup is expected constant time.
- You pay memory for the map, and you must define equality for the key.
- A nested loop is fine when the input is tiny or the extra memory is the problem.
A full answer
Start with the cost you can see. Two loops over n items do about n squared comparisons. If the interview is “find a pair that sums to a target,” that is acceptable for a few dozen rows and too slow when n is in the tens of thousands.
A hash map stores values you have already seen. For each new item you ask whether the complement is already in the map. Expected lookup is constant time, so the whole pass is linear. The map uses extra memory proportional to the input.
Say what the key is. For numbers, the key is the number. For objects, the key is the field you compare, and equal keys must land in the same bucket. If you forget that, the map will miss matches that a nested loop would find.
Close with the case you would not use the map. If n is small, the nested loop is clearer. If you are already at the memory limit, or the interviewer wants a sorted two-pointer solution with no extra space, say that and switch. The point is the tradeoff, not the data structure as a reflex.
Example
seen = empty map
for each value in the list:
if target - value is in seen:
return the pair
store value
return no pairMark your progress
Create a practice profile to mark this question.