3.3.10
Intuition The big idea (WHY hashing wins)Ek hash map aapko ==O ( 1 )
Frequency counting : "kya maine yeh pehle dekha hai? kitni baar?" → map key → count.Two-Sum : "kya jo complement mujhe chahiye woh pehle se exist karta hai?" → map value → index.LRU cache : "kya yeh key cached hai, aur least-recently-used victim kaun hai?" → map key → node.
Pattern hamesha same rehta hai: memory ko time ke liye trade karo — ek table mein answers yaad rakhke.
Ek frequency map (a.k.a. histogram / multiset) ek hash map count hai jahan count[x] store karta hai
ki element x kitni baar appear hua hai.
WHAT chahiye: ek list di gayi ho, toh har value kitni baar aai yeh jaanna.
WHY hash map: alternative (sort karo, phir runs scan karo) O ( n log n ) O ( n ) HOW : ek pass, count[x] += 1 (missing keys ke liye default 0).
Worked example "banana" mein letters count karob a n a n a
step
char
map after
Yeh step kyun?
1
b
{b:1}
pehli baar dikha → default 0, +1
2
a
{b:1,a:1}
naya key a
3
n
{b:1,a:1,n:1}
naya key n
4
a
{b:1,a:2,n:1}
a pehle dikh chuka → increment
5
n
{b:1,a:2,n:2}
n increment
6
a
{b:1,a:3,n:2}
a increment
Result: a:3, n:2, b:1. Kyun correct hai? Counts ka sum = 3 + 2 + 1 = 6 =
Worked example Pehla non-repeating character dhundho"leetcode" → frequency map {l:1,e:3,t:1,c:1,o:1,d:1}. String ko order mein re-scan karo, pehla
char return karo jiska count 1 ho → lKyun do passes? Pehla pass totals build karta hai; doosra pass
original order use karta hai. Total phir bhi O ( n )
Array nums aur target diya gaya ho, indices i, j (i ≠ j) return karo jaise ki
nums [ i ] + nums [ j ] = target .
Intuition Complement trickEk number x = nums[j] fix karo. Jo partner chahiye woh hai complement c = target − x kya maine value
c " — exactly ek hash-map lookup. Hum value → index store karte jaate hain.
def two_sum (nums, target): seen = {} # value -> index, of elements to the LEFT for j, x in enumerate (nums): c = target - x # the partner we need if c in seen: # O(1): did it appear earlier? return (seen[c], j) seen[x] = j # only record AFTER checking -> avoids using x twice return None
Worked example nums = [2, 7, 11, 15], target = 9
j
x
c=9−x
c in seen?
seen after
0
2
7
no
{2:0}
1
7
2
yes → (0,1) —
Yeh step kyun? j=1 par hum 2 dhundh rahe hain; woh j=0 par store tha, toh hum (0,1) return karte hain. Baaki scan karne ki zaroorat hi nahi padi. Answer: indices 0 aur 1.
Worked example "Store after check" kyun important hai: nums=[3,4], target=6Agar hum 3 ko check se pehle store kar dete toh uska complement 3 se match ho jaata, matlab index 0 apne aap se match ho jaata.
Pehle check karke (3 in {} → no), phir store karke, hum ek element ko do baar use hone se bachate hain.
Key→value ka ek fixed-capacity store jahan overflow hone par hum least recently used key ko evict karte hain.
Required ops dono O ( 1 ) get(key) aur put(key, value).
Intuition Kyun sirf ek hash map kaafi nahi haiEk hash map O ( 1 ) order ka koi notion nahi — woh nahi bata sakta kaun sa key
sabse pehle touch hua tha. Humein recency order bhi chahiye. Classic solution do structures combine karta hai:
ek hash map key → node O ( 1 )
nodes ki ek doubly linked list recency ke order mein (front = most recent, back = least recent)
O ( 1 ) O ( 1 )
Map node ko instantly locate karta hai; linked list instantly reorder/evict karta hai. Dono milke: O ( 1 )
class Node : def __init__ (self, k, v): self .k, self .v = k, v self .prev = self .next = None
class LRUCache : def __init__ (self, capacity): self .cap = capacity self .map = {} # key -> Node : O(1) lookup self .head = Node( 0 , 0 ) # sentinel: most-recent side self .tail = Node( 0 , 0 ) # sentinel: least-recent side self .head.next = self .tail self .tail.prev = self .head
def _remove (self, n): # unlink node : O(1) n.prev.next = n.next n.next.prev = n.prev
def _add_front (self, n): # insert right after head : O(1) n.next = self .head.next n.prev = self .head self .head.next.prev = n self .head.next = n
def get (self, key): if key not in self .map: return - 1 n = self .map[key] self ._remove(n); self ._add_front(n) # touched -> now most recent return n.v
def put (self, key, value): if key in self .map: self ._remove( self .map[key]) n = Node(key, value) self .map[key] = n self ._add_front(n) if len ( self .map) > self .cap: # over capacity -> evict lru = self .tail.prev # node just before tail = least recent self ._remove(lru) del self .map[lru.k]
Worked example capacity = 2
op
map keys
list (front→back)
note (Kyun?)
put(1,A)
{1}
1
naya, most recent
put(2,B)
{1,2}
2,1
2 newest, 1 older
get(1)→A
{1,2}
1,2
1 ko touch karne se woh front par aa gaya
put(3,C)
{1,3}
3,1
full! evict back = 2 (LRU)
get(2)→-1
{1,3}
3,1
2 evict ho gaya tha
Kyun 2 evict hua, 1 nahi? get(1) ke baad, key 1 most-recent ban gaya, jisse 2 back par reh gaya
least-recently-used ki tarah — toh jab 3 aaya toh wahi victim bana.
Common mistake Classic blunders ko steel-man karnaA. "Two-Sum: bas sort karo phir two-pointer use karo."
Kyun sahi lagta hai: two-pointer elegant hai aur O ( n log n ) Fix: sorting original indices destroy kar deta hai , lekin problem indices maangti hai. Tumhe (value,index) pairs store aur recover karne padte — extra kaam. Hash map O ( n )
B. "Two-Sum: value ko map mein check se pehle store karo."
Kyun sahi lagta hai: "sab kuch add karo, phir sab available hai." Fix: ek element apne aap se match ho sakta hai (e.g. target=6, value=3 ek baar). Hamesha pehle complement check karo, baad mein insert karo.
C. "LRU ke liye sirf ek hash map kaafi hai."
Kyun sahi lagta hai: map already O ( 1 ) Fix: usmein order nahi hai, toh least-recently-used key dhundna O ( n )
D. "Frequency: map ki jagah array mein index karo."
Kyun sahi lagta hai: arrays ke constants faster hote hain jab keys small ints hon. Fix: valid sirf tab jab key space small/dense ho (e.g. 26 letters). Arbitrary/large/string keys ke liye, hash map general tool hai.
Recall Feynman: ek 12-saal ke bachche ko samjhaoSocho ek magic notebook hai jahan tum instantly kisi bhi naam par flip kar sakte ho aur uske saath ek number dekh sakte ho.
Counting: jab bhi tum koi dost dekho uske naam ke saath 1 add karo — end mein pata chalega kaun sabse zyada aaya. Two-Sum: tum chahte ho do cards jo 10 tak add hon; har card ke liye check karo "kya maine pehle se 10-minus-yeh card dekha?" — notebook instantly jawab deti hai. LRU: tumhara toy box sirf 2 toys fit karta hai; jo toy tumne sabse haal mein kheli woh top par rakhte ho, aur jab naya toy aata hai tum woh toy phenkh dete ho jo sabse neeche thi aur jise tum sabse zyada ignore karte the. Notebook instantly batati hai har toy kahan hai.
Mnemonic Teen patterns yaad karo"Count, Complement, Cache" — sab C se start hote hain aur sab Cache an answer karte hain:
Count → key→count Complement → key→index (target−x dhundho)Cache(LRU) → key→node (+ recency list)
Two-Sum O ( n ) O ( n 2 )
LRU mein list ka kaun sa end evict hota hai? 4. Two-Sum mein check ke baad insert kyun karte hain?
Frequency map kya store karta hai? key → kitni baar woh key appear hui; ek O ( n )
n items aur k distinct ke saath frequency counting ka time aur space? Time O ( n ) O ( k ) k = n
Two-Sum mein x ka "complement" kya hai? c = target − x
Hash-map Two-Sum O ( n ) O ( n 2 ) Har index ek O ( 1 )
Two-Sum mein complement check karne ke BAAD seen mein insert kyun karte hain? Ek element ko apne aap se match hone se bachane ke liye (ek element do baar use ho jaata).
Kyun ek plain hash map akele LRU cache implement nahi kar sakta? Usmein recency order nahi hai, toh least-recently-used key dhundna O ( n )
O ( 1 ) Ek hash map (key→node) aur ek doubly linked list recency ke order mein.
LRU ke liye doubly (singly nahi) linked list kyun? Kisi arbitrary node ko O ( 1 )
LRU list mein kaun sa end evict hota hai aur kyun? Back (tail sentinel se thoda pehle) — woh least recently used hota hai.
Successful get par LRU node ke saath kya karta hai? Use remove karta hai aur front par re-add karta hai (use most recently used mark karta hai).
Frequency counting ke liye hash map ki jagah array kab better hoti hai? Jab keys small, dense integers hon (e.g. 26 lowercase letters).
In applications mein hashing ka general trade-off kya hai? Memory trade karo (O ( n ) O ( 1 )
Hash Functions — O ( 1 ) Collision Resolution (Chaining vs Open Addressing) — kyun "average" O ( 1 ) Doubly Linked List — LRU mein recency ordering engineSliding Window — frequency maps ke saath aksar pair hota hai (anagrams, longest substring)Time Complexity Analysis — O ( n ) O ( n 2 ) O ( n log n ) Caching Strategies — LRU vs LFU vs FIFO eviction policies
Invariant seen holds prior indices
Least-recently-used victim
