Trade a little memory for a lot of speed by remembering what you have already seen.
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.
9: the pair is found when the second of the two numbers arrives. Why not the first?100: the loop finishes without a pair. What does the map look like at the end?3, 3 with target 6. Why does it work?5 with target 10 (a single 5). Does it wrongly pair with itself? Watch the order: lookup comes before store.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.