Intuition The one core ideaA hash map is a magic filing cabinet that jumps straight to the drawer you ask for — no searching. Almost every trick in this chapter (counting, two-sum, LRU) is just "remember what you've seen in that cabinet so you never look twice."
Before you can read the parent note on Applications , every symbol on that page must mean something concrete to you. Below we build them one at a time — each from the picture it stands for.
Definition Key, value, mapA map (a.k.a. dictionary) is a collection of (key → value) pairs. The key is the label you look things up by; the value is the stuff stored under that label. You give a key, you get back its value.
The picture: a wall of labelled drawers. The label on the drawer is the key ; whatever is inside is the value .
Intuition Why "hash"? What makes the jump instantA hash function turns a key (a word, a number, anything) into a drawer number. Instead of walking past every drawer reading labels, you compute which drawer to open and go straight there.
The picture: a little machine. You feed in the word "banana", out pops the number 3, so you open drawer 3 immediately. That "compute-then-jump" is why lookup does not depend on how many drawers exist. For the machine's inner workings see Hash Functions ; for what happens when two keys land on the same drawer see Collision Resolution (Chaining vs Open Addressing) .
The parent note is soaked in these. They describe how work grows as the input grows — nothing more.
Definition Big-O, in plain wordsO ( something ) shape of the growth of the running time, ignoring constant factors. Read O ( f ( n )) like f ( n ) n
Here n how big the input is (how many items in the list).
Intuition Each one, as a picture of effort
O ( 1 ) flat . One drawer-open. Same effort for 10 items or 10 million. This is the hash-map lookup.O ( n ) straight ramp . Touch every item once. One pass through the list.O ( n log n ) gentle bend upward . The cost of a good sort.O ( n 2 ) steep bowl . Every item paired with every other item — the brute-force two-sum.
O ( 1 ) does not grow with n . It could be 50 machine steps; the point is it stays 50 whether n collision can spoil it in the rare worst case.
The cost formulas use i = 1 ∑ n O ( 1 )
Definition Sigma / summationi = 1 ∑ n (thing) i n i 1 n
The picture: a tally. Loop the counter i = 1 , 2 , 3 , … , n
Worked example Unpacking the frequency-count cost∑ i = 1 6 O ( 1 ) = O ( 1 ) + O ( 1 ) + O ( 1 ) + O ( 1 ) + O ( 1 ) + O ( 1 ) = 6 ⋅ O ( 1 ) = O ( 6 ) = O ( n ) . "banana", one flat unit of work each → linear total. The constant 6 shape .
Brute-force two-sum costs ( 2 n )
The picture: a handshake room. n ( 2 n )
O ( n 2 ) 2 n ( n − 1 ) = 2 n 2 − n n n 2 2 1 − n ( 2 n ) = O ( n 2 )
nums is a list; ==nums[i]== is "the element sitting in position i 0 nums[0] is the first element. The number i index (the address), not the value stored there.
i = j i j different positions ." Two-sum wants two different slots that add to the target, so you cannot use one number twice.
enumerate gives you
In for j, x in enumerate(nums) the loop hands you both the position j and the value x = nums[j] at the same time. Picture a moving pointer sliding left-to-right: j is where the finger is, x is what it's pointing at. The map seen remembers everything to the left of the finger — this "window of the past" idea connects to Sliding Window .
Given a value x and a target, the complement is the partner number you'd need so the two add up:
c = target − x , x + c = target .
The picture: a seesaw that must balance at height target. If one side sits at x, the other side must sit at c = target − x. Two-sum's whole cleverness is: instead of searching for a matching pair , search for this single required number c in the map of things seen so far.
The LRU section needs a Doubly Linked List . Here is its alphabet.
Definition Node, prev, nextA node is a little box holding a value plus two arrows: ==next points to the box after it, prev== points to the box before it. Follow next arrows and you walk forward; follow prev you walk back.
Definition Sentinel (head / tail)A sentinel is a fake node with no real data, parked permanently at each end so the real nodes always have a neighbour on both sides. The parent's head guards the "most-recent" end; tail guards the "least-recent" end.
The picture: a train. Two dummy locomotives (sentinels) bookend the carriages so you never fall off either end. To yank a carriage out you only need to re-link its two neighbours — that is the O ( 1 )
Common mistake "The sentinels store real keys"No. Node(0,0) head/tail hold dummy 0s that never appear in the map. They exist only so head.next and tail.prev are always valid — no special-casing an empty list.
Hash function turns key into slot
Summation adds cost per item
Why brute force is O of n squared
Complement target minus x
Doubly linked list prev and next
Cover the right side; can you answer before revealing?
What does O ( 1 ) The effort does not grow with input size n
What is a hash function's job? Turn a key into a slot number so you jump straight to it instead of scanning.
What does i = 1 ∑ n O ( 1 ) O ( n ) n
Why is ( 2 n ) O ( n 2 ) It equals 2 n ( n − 1 ) = 2 n 2 − n n 2 n
What is the complement c c = target − x x + c = target
Why must i = j You need two different positions; one element can't pair with itself.
What extra info does a doubly linked list store vs a singly linked one? Each node keeps prev (its predecessor), enabling O ( 1 )
What is a sentinel node for? A dummy end-guard so real nodes always have neighbours on both sides — no empty-list special cases.
Which end of the LRU list is the eviction victim? The node at tail.prev — the least-recently-used, just before the tail sentinel.
