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

Tool: a hash map used as a frequency map. Key = the word (a string), value = the running count (an integer). Why this and not sorting? Sorting all words to group duplicates costs $O(n\log n)$; a map counts in $O(n)$ because each lookup/increment is $O(1)$ average (see Time Complexity Analysis). One pass: for each word w, do count[w] += 1 (missing → default 0).

Look up the complement $c=\text{target}-x=10-4=6$. The map stores value → index of every element strictly to the left of the current one. The question "is a valid partner already available?" is literally "is $6$ a key in the map?".

Walk left to right, incrementing each character:

Final counts: m:1, i:4, s:4, p:2. Check: $1+4+4+2=11=$ length, so nothing was lost. First non-repeating: re-scan the original string in order and return the first char whose count is $1$. That is m (position 0). Why two passes? Pass 1 builds totals; pass 2 uses the original left-to-right order to break ties. Still $O(n)$ total.

Recall the invariant: when we reach index $j$, seen holds exactly nums[0..j-1].

At $j=2$ the complement $2$ was stored at index $1$, so the answer is (1, 2). Note we did not match the first 3 with itself: at $j=0$ we checked before inserting, and seen was empty.

Final: list order 4,3; map keys {3,4}. get(2) returns -1 (miss). Why 1 was the victim at put(4)? After put(3), the back was 1 (it hadn't been touched since get(1)), so it became the least-recently-used and got evicted.

Flaw: the problem asks for the original indices, but sorting destroys them. To recover indices you must sort (value, index) pairs, which reintroduces $O(n)$ auxiliary space — so the promised $O(1)$ space is not real for this problem. Also the sort costs $O(n\log n)$. Correct hash cost: time $T_{\text{hash}}={\sum }_{j=0}^{n-1}O(1)=O(n)$, space $O(n)$ for the map. So hashing is asymptotically faster ($O(n)$ vs $O(n\log n)$) and keeps indices for free.

To make a touched node "most recent" in $O(1)$, we must first splice it out of its current spot. Splicing requires rewiring the node before it — its predecessor.

• A Doubly Linked List stores prev, so the predecessor is known instantly: $\text{node.prev.next}=\text{node.next},\text{node.next.prev}=\text{node.prev}.$ Two pointer writes → $O(1)$.
• A singly linked list has no prev; to find the predecessor you would scan from the head, which is $O(n)$. That would break the $O(1)$ contract for get/put.

Time: every element triggers one hash + one map update, each $O(1)$ average, so $T(n)={\sum }_{i=1}^{n}O(1)=O(n)$. Space: the map holds one entry per distinct key: $O(k)$. Worst case space: when all values are distinct, $k=n$, giving $O(n)$. (See Collision Resolution (Chaining vs Open Addressing) for why "average $O(1)$" can degrade to $O(n)$ per op under adversarial collisions — the map may need resizing/good hashing to hold.)

Idea: keep a window [L..R] with all-distinct chars. Store last[ch] = last index seen. When the char at R was seen inside the window, jump L to last[ch] + 1 (never move L backward). Track the max window width.

Max width = 3, achieved by substring "abc". Each of L, R moves forward at most $n$ times → $O(n)$. The map gives $O(1)$ "have I seen this char, and where?".

Values summing to 6: pairs of complements are (1,5) and (3,3). Build frequency map: {1:1, 5:2, 3:2}.

• Distinct complements a + b = 6, a < b: only 1 + 5. Count = $\text{freq}[1]\times \text{freq}[5]=1\times 2=2$ pairs.
• Equal halves a = b = 3: choose 2 of the two 3's = $\left(\genfrac{}{}{0ex}{}{\text{freq}[3]}{2}\right)=\left(\genfrac{}{}{0ex}{}{2}{2}\right)=1$ pair. Total = $2+1=3$ unordered pairs. Why the $\left(\genfrac{}{}{0ex}{}{f}{2}\right)$ for equal halves? A value can't pair with itself using the same index; we count distinct index pairs among the $f$ copies.

Use the same map + Doubly Linked List design. Keep a head sentinel on the most-recent side. Then getMostRecent() = head.next.k — the node immediately after the head is always the newest. It is $O(1)$ because it's a single pointer dereference; every get/put already maintains the invariant "front = most recent" by splicing touched nodes right behind head. No scan needed. (Symmetrically, the least recent is tail.prev.k, which is exactly the eviction victim.)

Final state: map {2:C}, list 2. Why put(2,C) does not evict? Key 2 already exists, so we _remove its old node and re-add — the map size never exceeds capacity, so no eviction fires. This is the degenerate capacity-1 case the design must still handle correctly.

• "": the frequency map is empty; the second pass has nothing to scan, so there is no non-repeating character → return a sentinel such as -1 / None. (Handle the empty case explicitly.)
• "aabb": frequency map {a:2, b:2}. Every count is $\ge 2$, so the second pass finds no char with count 1 → return -1 / None. The result "no unique char exists" is a valid, non-crashing outcome the caller must expect.

Frequency counting ::: a tally sheet: one line per distinct thing, add a stroke each time you see it. Two-Sum complement ::: "I need a friend who adds up to the target — have I already met them?" LRU pairing ::: the map is a phone book (find fast); the linked list is a queue of who you called last (evict fast).