HashMap
Store seen values so you can find the missing complement in one pass.
0 of 3 problems solved
HashMap
Store seen values so you can find the missing complement in one pass.
- •Do I need to remember values I already saw?
- •Can I turn the target into a missing complement?
- •Would a HashMap avoid a nested loop?
Two Sum looks scary at first because your brain wants to compare every number with every other number. That works, but it is slow. The smarter idea is this: for each number, ask 'what number do I still need to reach the target?' Then use a HashMap like a tiny memory box to remember what you have already seen. Instead of searching the whole array again, you do one quick lookup and move on.
The real trick is to search for the missing piece, not to test every possible pair.
- 1Walk through the array once from left to right.
- 2For the current number, compute the complement: target minus current number.
- 3Check whether that complement is already in your HashMap.
- 4If it is, you found the pair. If it is not, store the current number and keep going.
Storing the current number before checking its complement can accidentally pair a number with itself. Check first, then store.
Top K Frequent Elements
Build a frequency map first, then select the top k entries. A min-heap of size k or a bucket approach avoids sorting the entire map.
LRU Cache
You need O(1) get AND O(1) ordered removal. HashMap for instant key access, doubly-linked list for O(1) move-to-front and tail eviction.