Applications — frequency counting, two-sum problem, caching (LRU)

1. Frequency Counting

WHAT we want: given a list, know how often each value occurs. WHY a hash map: the alternative (sort, then scan runs) is $O(n\log n)$ ; counting in a map is $O(n)$ . HOW: one pass, count[x] += 1 (defaulting missing keys to 0).

Worked example Count letters in "banana"

b a n a n a

step	char	map after	Why this step?
1	b	{b:1}	first sight → default 0, +1
2	a	{b:1,a:1}	new key a
3	n	{b:1,a:1,n:1}	new key n
4	a	{b:1,a:2,n:1}	a seen before → 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. Why correct? Sum of counts $=3+2+1=6=$ length, so nothing lost.

2. Two-Sum Problem

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)	—

Why this step? At j=1 we look for 2; it was stored at j=0, so we return (0,1). We never needed to scan the rest. Answer: indices 0 and 1.

3. LRU Cache (Least Recently Used)

Figure — Applications — frequency counting, two-sum problem, caching (LRU)

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 (Why?)
put(1,A)	{1}	1	new, most recent
put(2,B)	{1,2}	2,1	2 newest, 1 older
get(1)→A	{1,2}	1,2	touching 1 moves it to front
put(3,C)	{1,3}	3,1	full! evict back = 2 (LRU)
get(2)→-1	{1,3}	3,1	2 was evicted

Why 2 was evicted, not 1? After get(1), key 1 became most-recent, leaving 2 at the back as least-recently-used — so it's the victim when 3 arrives.

Common mistake Steel-manning the classic blunders

A. "Two-Sum: just sort then two-pointer." Why it feels right: two-pointer is elegant and $O(n\log n)$ . The fix: sorting destroys the original indices, but the problem asks for indices. You'd need to store (value,index) pairs and recover them — extra work. The hash map keeps indices for free in $O(n)$ .

B. "Two-Sum: store the value in the map before checking." Why it feels right: "add everything, then it's all available." The fix: you can match an element with itself (e.g. target=6, value=3 once). Always check the complement first, insert after.

C. "LRU only needs a hash map." Why it feels right: the map already does $O(1)$ get/put. The fix: it has no order, so finding the least-recently-used key would cost $O(n)$ . You need the linked list (or an ordered map) for recency.

D. "Frequency: index into an array instead of a map." Why it feels right: arrays are faster constants when keys are small ints. The fix: valid only when the key space is small/dense (e.g. 26 letters). For arbitrary/large/string keys, a hash map is the general tool.

Recall Feynman: explain to a 12-year-old

Imagine a magic notebook where you can flip instantly to any name and see a number next to it. Counting: every time you see a friend you add 1 next to their name — at the end you know who showed up most. Two-Sum: you want two cards adding to 10; for each card you check "did I already see a 10-minus-this card?" — the notebook answers instantly. LRU: your toy box only fits 2 toys; you keep the toy you played with most recently at the top, and when a new toy comes you throw out the one at the bottom that you ignored longest. The notebook tells you instantly where each toy is.

Flashcards

What does a frequency map store?

key → number of times that key has appeared; built in one

O(n)

pass.

Time & space of frequency counting n items with k distinct?

Time

O(n)

, Space

O(k)

(worst

k=n

In Two-Sum, what is the "complement" of x?

c = \text{target} - x

; the partner value needed to reach the target.

Why is hash-map Two-Sum

O(n)

vs brute

O(n^2)

Each index does one

O(1)

complement lookup instead of scanning all later elements.

Why insert into seen AFTER checking the complement in Two-Sum?

To prevent matching an element with itself (using one element twice).

Why can't a plain hash map implement an LRU cache alone?

It has no recency order, so finding the least-recently-used key would be

O(n)

Which two data structures combine to make an

O(1)

LRU cache?

A hash map (key→node) plus a doubly linked list ordered by recency.

Why doubly (not singly) linked list for LRU?

To unlink an arbitrary node in

O(1)

you need its predecessor pointer (prev).

In the LRU list, which end is evicted and why?

The back (just before the tail sentinel) — it is the least recently used.

On a successful get, what does LRU do to the node?

Removes it and re-adds it to the front (marks it most recently used).

When is an array preferable to a hash map for frequency counting?

When keys are small, dense integers (e.g. 26 lowercase letters).

General hashing trade-off these applications exploit?

Trade memory (

O(n)

table) for

O(1)

average-time lookups.

Connections

Hash Functions — the $O(1)$ average lookup that powers all three apps
Collision Resolution (Chaining vs Open Addressing) — why "average" $O(1)$ , not worst-case
Doubly Linked List — recency ordering engine in LRU
Sliding Window — frequently pairs with frequency maps (anagrams, longest substring)
Time Complexity Analysis — $O(n)$ vs $O(n^2)$ vs $O(n\log n)$ comparisons
Caching Strategies — LRU vs LFU vs FIFO eviction policies

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hashing ka asli superpower yeh hai ki ek hash map mein lookup, insert aur delete average mein $O(1)$ hote hain. Bas isi ek cheez se teen alag problems aasaan ho jaati hain. Pehla: frequency counting — har element pe count[x] += 1 karo, ek hi pass mein pata chal jaata hai kaunsa item kitni baar aaya. Pure sorting ki zarurat nahi, $O(n)$ mein kaam ho gaya.

Doosra: Two-Sum. Yahan trick hai complement. Agar target $T$ hai aur abhi number $x$ dekh rahe ho, to tumhe chahiye partner $c = T - x$ . To question banta hai "kya yeh $c$ maine pehle dekha hai?" — yeh hash map se turant pata chalta hai. Isliye brute force $O(n^2)$ ki jagah hum $O(n)$ mein nikaal lete hain. Yaad rakho: pehle complement check karo, phir current number ko map mein daalo — warna ek element apne aap se match ho jaayega (galti!).

Teesra: LRU cache. Sirf hash map se kaam nahi chalega, kyunki map ko order nahi pata — kaun sa key sabse purana (least recently used) hai yeh batane ke liye usse $O(n)$ lagega. Isliye hum hash map ke saath ek doubly linked list jodte hain: front pe most-recent, back pe least-recent. Map se node turant mil jaata hai, aur linked list se use front pe le jaana ya back wala evict karna dono $O(1)$ . Doubly isliye chahiye kyunki node ko beech se nikaalne ke liye uska prev pointer chahiye. Short trick yaad rakho: "Count, Complement, Cache" — teeno C, teeno answer ko cache karte hain.

Applications — frequency counting, two-sum problem, caching (LRU)

1. Frequency Counting

2. Two-Sum Problem

3. LRU Cache (Least Recently Used)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Hashing

Connections