Hash Map: Two Sum

Trade a little memory for a lot of speed by remembering what you have already seen.

The idea

You are at a party looking for two guests whose ages add to 30. Slow way: compare every guest with every other guest. Smart way: as each guest arrives, ask “has someone aged (30 − my age) already arrived?” If you keep a notebook of arrivals (a hash map), that question is answered instantly. If yes, you are done. If not, write this guest in the notebook and move on.

Watch it work

Try it

Common mistakes

How fast is it?

Time: O(n) – one pass, and each map lookup/insert is O(1) on average. Space: O(n) – the map may hold every number. The brute-force double loop is O(n²) time but O(1) space.