What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Advanced Data Structures Foundation • Invariant Proof & Speed-Run

Theory Context•Advanced Data Structures

Conceptual Foundation & Intuitive Analogy

Advanced Data Structures conquer the problems where standard arrays, hash maps, and binary heaps fail: multi-dimensional state coordination, dynamic equivalence clustering, and strict sub-linear retrieval.

🧭 Conceptual Foundation & Pattern Intuition

Standard data structures are single-dimensional: a hash table offers $O(1)$ point lookups but cannot answer prefix queries or maintain order without $O(N)$ re-scans. A binary search tree maintains order but pays $O(\log N)$ per query and degrades without complex self-balancing. The Advanced Data Structures cluster synthesizes specialized topological pointer arrangements to break these trade-offs:

Prefix Trees (Tries): Exploit common character subpaths to guarantee string insertion, exact search, and prefix validation in $O(L)$ time proportional strictly to string length, independent of dictionary size.
Disjoint Set Union (DSU / Union-Find): Tracks dynamic equivalence classes and connected components in near-constant $O(\alpha(N))$ amortized time using tree flattening (path compression) and tree balancing (union-by-rank).
Composite Caches (LRU, LFU, All O`one): Couples hash maps with doubly-linked lists and frequency buckets to deliver simultaneous $O(1)$ key lookup and $O(1)$ ordered eviction.

🏙️ The Analogy: The Metropolitan Public Transit & Archive System

Think of a city infrastructure system:

A Trie is the city's postal routing hub: letters destined for "101 Main St", "101 Market St", and "101 Michigan Ave" all travel down the exact same highway corridor ("101 M...") before branching off at the final block. Words with a shared prefix share the same path.
Union-Find is the regional marriage and civil registry: instead of asking every person if they are related to someone else by tracing an entire family tree, every person simply names their community's recognized village elder (canonical root). If two people name the same elder, they belong to the same clan.
LRU/LFU Caches are the tiered express warehouses: an inventory clipboard (hash map) tells the forklift driver the exact shelf coordinates of any pallet, while a physical conveyor belt (doubly linked list) automatically moves accessed items to the front and pushes dusty, untouched pallets toward the donation chute at the back.

🔑 Why It Works

Each paradigm couples an $O(1)$ entry map with an localized structural invariant, bypassing $O(N)$ brute-force scans.

Visual Blueprint & State Transition Model

Advanced Data Structures Mental Model Diagram — Figure 1 • Advanced Data Structures Core Invariant & State Lifecycle

Core Invariant Specification

Trie: "A node's is_end flag, not its existence, is what says a word was stored here." Union-Find: "Two elements are connected exactly when find(a) == find(b). Nothing else in the structure means anything."

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

The 8 Mental Models of Advanced Data Structures

Select the specialized data structure based on query semantics.

1Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Trie (Prefix Tree)

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Mode 1 · Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Words that share a prefix share one path from root, so any prefix is found by walking one child per letter. insert creates missing children with setdefault and sets is_end on the last node; search and startsWith share _walk. This is correct because a path exists exactly when some inserted word has that prefix, and is_end marks exactly the nodes where a whole word stopped. The trap is skipping is_end in search: after inserting "apple", search("app") would return true.

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Canonical LeetCode:Implement Trie (Prefix Tree) (LC 208)Design Add and Search Words Data Structure (LC 211)Word Search II (LC 212)Stream of Characters (LC 1032)Implement Trie II (Prefix Tree) (LC 1804)Design Search Autocomplete System (LC 642)Longest Word in Dictionary (LC 720)Longest Common Prefix (LC 14)

Open the Trie card

2Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Union-Find (Disjoint Set Union)

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Mode 2 · Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Name each group by the root of its tree: find follows parent links up to the root, and union joins two groups by pointing one root at the other. Two items are connected exactly when find returns the same root for both, so union returns False when ra == rb, which is how an edge that closes a cycle is detected. Path compression in find and hanging the smaller tree under the larger (size) keep every tree shallow. The trap is linking the items instead of their roots: always link rb under ra after both find calls, never self.parent[b] = a.

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Canonical LeetCode:Redundant Connection (LC 684)Number of Provinces (LC 547)Accounts Merge (LC 721)Number of Islands II (LC 305)Most Stones Removed with Same Row or Column (LC 947)The Earliest Moment When Everyone Become Friends (LC 1101)Number of Operations to Make Network Connected (LC 1319)Lexicographically Smallest Equivalent String (LC 1061)Redundant Connection II (LC 685)Graph Valid Tree (LC 261)Number of Connected Components in an Undirected Graph (LC 323)Evaluate Division (LC 399)

Open the Union-Find card

3LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

LRU Cache (HashMap + Doubly Linked List)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

Mode 3 · LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

The hash map finds any node instantly, and the doubly linked list keeps nodes in order of use: most recent next to head, least recent next to tail. This is correct because every get and every put moves its node to the front, so no node can sit behind one that was used less recently, and the node just before tail is always the least recently used; each node stores its key so evicting it can also del self.cache[lru.key]. The trap is put on a key that is already there: update node.val and move the node to the front, or it keeps its old place and is evicted too early; with capacity 2, put(1, 1), put(2, 2), put(1, 9), put(3, 3) must evict 2, not 1.

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)

Open the LRU Cache card

4Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Array + Index Map (Swap-with-Last Delete)

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Mode 4 · Insert Delete GetRandom

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

A pick where every value is equally likely needs the values packed in a list, random.choice(self.values), and a list can only drop its last slot without shifting the rest, so remove fills the hole with the last value instead of shifting: self.values[i] = last, then self.values.pop(). A set has no order, so moving one value changes nothing a caller can see, and self.index finds i with one lookup; the list stays gap-free, so every value keeps exactly one slot and the same 1-in-n chance. The trap is the order of the two map writes: self.index[last] = i must come before del self.index[val]. When val is itself the last value, last == val, and deleting first writes val straight back into the map at a slot that pop() removes, so a later insert(val) returns False.

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Open the Insert Delete GetRandom card

5Fenwick Tree

array ➔ isolate lowbit = x & (-x) ➔ O(log N) prefix query & update

Fenwick Tree (Binary Indexed Tree)

Spot it when: The array changes (single-element updates) and you still need prefix or range sums fast, or you count how many earlier values are smaller as you go.

Mode 5 · Fenwick Tree

Python

1	class FenwickTree:
2	"""Binary Indexed Tree (Fenwick Tree) for 1-indexed range sums.
3	Time: O(log N) update & query \| Space: O(N)
4	"""
5	def __init__(self, n: int):
6	self.n = n
7	self.tree = [0] * (n + 1)
8
9	def update(self, i: int, delta: int) -> None:
10	"""Add delta to index i (1-indexed)."""
11	# 1. Walk Up, Fixing Every Block That Covers i:
12	# Adding the lowest set bit jumps from i to the next larger block that still contains it,
13	# so this visits exactly the blocks whose stored sum needs delta added.
14	while i <= self.n:
15	self.tree[i] += delta
16	i += i & (-i) # Step up to parent covering range
17
18	def query(self, i: int) -> int:
19	"""Sum elements from 1 to i (1-indexed)."""
20	total = 0
21
22	# 1. Walk Down, Adding Disjoint Blocks:
23	# Removing the lowest set bit jumps to just before the block tree[i] covers, so each block
24	# added is disjoint from the ones before it, and together they cover exactly 1..i once.
25	while i > 0:
26	total += self.tree[i]
27	i -= i & (-i) # Step down to next disjoint prefix
28	return total
29
30	def range_query(self, left: int, right: int) -> int:
31	"""Sum in range [left, right] inclusive."""
32	return self.query(right) - self.query(left - 1)
33
34
35	class NumArray:
36	"""Range Sum Query - Mutable: keep the values, send each change to the Fenwick tree."""
37	def __init__(self, nums: list[int]):
38	self.nums = list(nums)
39	self.fenwick = FenwickTree(len(nums))
40
41	# 1. Seed The Tree With Every Starting Value:
42	# Each 0-based position lives one slot higher in the 1-indexed tree, so index + 1 is its i.
43	for index, val in enumerate(nums):
44	self.fenwick.update(index + 1, val) # Position index lives at i = index + 1
45
46	def update(self, index: int, val: int) -> None:
47	self.fenwick.update(index + 1, val - self.nums[index]) # Add the change, not the new value
48	self.nums[index] = val
49
50	def sumRange(self, left: int, right: int) -> int:
51	return self.fenwick.range_query(left + 1, right + 1)

Let tree[i] hold the sum of the block of i & (-i) values that ends at position i: query adds whole blocks while i -= i & (-i) walks down, and update fixes every block that contains i while i += i & (-i) walks up. Removing the lowest set bit jumps to just before the block tree[i] covers, so the blocks query visits never overlap and together cover exactly 1..i; adding it lands on the next larger block that also contains i. The trap is index 0: the tree is 1-indexed, and i & (-i) is 0 when i is 0, so update(0, ...) never moves and loops forever; shift every position up by one.

Gotchas1 of 5

The trap
Gotcha 1: Calling update(index, val) with a 0-based index
Mistake
```
self.fenwick.update(index, val)
```
Fix
```
self.fenwick.update(index + 1, val)
```
What happens: The tree is 1-indexed. For i = 0, i & (-i) is 0, so i += i & (-i) leaves i at 0. The loop while i <= self.n then never ends. Shift every position up by one, so nums[index] lives at i = index + 1.
Example: nums = [1, 3, 5], then sumRange(0, 2)
Mistake: the loop never endsFix: returns 9
Gotcha 2: Shifting right but not left in sumRange
Mistake
```
return self.fenwick.range_query(left, right + 1)
```
Fix
```
return self.fenwick.range_query(left + 1, right + 1)
```
What happens: range_query(left, right) returns query(right) - query(left - 1). With left not shifted, it subtracts the sum up to position left - 1. Position left - 1 holds nums[left - 2], so the result also counts nums[left - 1].
Example: nums = [1, 3, 5], then sumRange(1, 2)
Mistake: returns 9Fix: returns 8
Gotcha 3: Adding the new value instead of the change
Mistake
```
self.fenwick.update(index + 1, val)
```
Fix
```
self.fenwick.update(index + 1, val - self.nums[index])
```
What happens: FenwickTree.update adds delta to a position. It can't set a value. To change nums[index] to val, add val - self.nums[index]. The blueprint keeps the current values in self.nums for this subtraction.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 11Fix: returns 8
Gotcha 4: Using raw values as positions instead of ranks 1..m
What happens: In Count of Smaller Numbers After Self (LC 315), the values can be negative or 0. From a position of 0 or below, i += i & (-i) reaches 0 and stays there. So update never ends. Replace each value by its rank 1..m among the sorted distinct values first. Then scan nums from the right.
Gotcha 5: Building with n calls to update when O(n) is needed
Mistake
```
for index, val in enumerate(nums):
    self.fenwick.update(index + 1, val)
```
Fix
```
for i in range(1, n + 1):
    self.tree[i] += nums[i - 1]
    parent = i + (i & -i)
    if parent <= n:
        self.tree[parent] += self.tree[i]
```
What happens: Each update visits up to log n positions, so n calls cost O(n log n) time. The one-pass build adds each tree[i] into its parent i + (i & -i) once. It gives the same tree in O(n) time. The sums are the same, and only the time changes.

Canonical LeetCode:Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)Range Sum Query 2D - Mutable (LC 308)Queries on a Permutation With Key (LC 1409)Reverse Pairs (LC 493)Create Sorted Array through Instructions (LC 1649)

Open the Fenwick Tree card

6Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Ordered Set (Floor/Ceiling Lookups)

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Mode 6 · Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Keep the stored keys sorted however they arrive, so one bisect_right finds both neighbours of a new value: the floor at i - 1 and the ceiling at i. For a calendar that is all you need: stored events never overlap, so sorted by start they are sorted by end too, and every other event either ends before the floor starts or starts after the ceiling. A new event fits exactly when the floor has ended by startTime and the ceiling starts no earlier than endTime; then it is inserted at i in both starts and ends. The trap is the half-open ends: the checks are self.ends[i - 1] > startTime and self.starts[i] < endTime, strict, because an event ending at 20 and one starting at 20 share no moment.

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

What happens: A rejected event must leave no trace. If it is inserted first and then rejected, it stays in self.starts and self.ends. Later events that overlap only the rejected one are then rejected too.

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)

Open the Ordered Set card

7Merge Sort Counting

pairs i < j ➔ count across two sorted halves ➔ merge

Merge Sort Counting (Reverse Pairs, Count of Range Sum)

Spot it when: You must count pairs of positions i < j whose values satisfy a comparison (an earlier value bigger than a later one, more than twice it, or a difference within a range), and checking every pair is too slow.

Mode 7 · Merge Sort Counting

Python

1	def reverse_pairs(nums: list[int]) -> int:
2	"""Reverse Pairs: count the pairs that cross the middle while both halves are sorted, then merge.
3	Time: O(N log N) \| Space: O(N)
4	"""
5	def sort_count(lo: int, hi: int) -> int:
6	# 1. Handle One Value, Then Count Each Half On Its Own:
7	# A range of one value holds no pair; otherwise the recursive calls count every pair
8	# that does not cross this range's middle, and hand back two sorted halves.
9	if hi - lo <= 1:
10	return 0
11	mid = (lo + hi) // 2
12	count = sort_count(lo, mid) + sort_count(mid, hi)
13
14	# 2. Count The Pairs That Cross The Middle, While Both Halves Are Still Sorted:
15	# nums[i] only grows as i moves through the sorted left half, so the right values
16	# that pair with it, nums[mid:j], can only grow too; j never has to move back.
17	j = mid
18	for i in range(lo, mid):
19	while j < hi and nums[i] > 2 * nums[j]:
20	j += 1
21	count += j - mid
22
23	# 3. Merge The Two Sorted Halves, Now That Counting Is Done:
24	# The merge moves by plain order, nums[a] <= nums[b], not by the pair's own test, so
25	# counting must happen first, in its own pass; merging afterwards hands the parent a
26	# sorted range.
27	merged: list[int] = []
28	a, b = lo, mid
29	while a < mid and b < hi:
30	if nums[a] <= nums[b]:
31	merged.append(nums[a])
32	a += 1
33	else:
34	merged.append(nums[b])
35	b += 1
36	merged.extend(nums[a:mid])
37	merged.extend(nums[b:hi])
38	nums[lo:hi] = merged
39	return count
40
41	return sort_count(0, len(nums))

Every pair i < j either sits inside one half of the range or crosses its middle, so let the recursive calls count the pairs inside each half and count only the crossing pairs yourself, at the moment both halves come back sorted. Sorted halves are what make that fast: the right values that pair with nums[i] form a prefix nums[mid:j] of the right half, and as nums[i] grows through the sorted left half that prefix only grows, so one pointer j that never moves back counts all of them with count += j - mid; merging afterwards hands the parent a sorted range, which keeps the argument true one level up. The trap is counting inside the merge loop, the way inversions are counted: the merge moves by nums[a] <= nums[b], not by the pair's own test nums[i] > 2 * nums[j], so on [3,5,2,1] it misses 5 > 2 * 2 and returns 2 instead of 3. Count in a separate pass, then merge.

Gotchas1 of 5

The trap
Gotcha 1: Counting pairs inside the merge loop
Mistake
```
else:
    if nums[a] > 2 * nums[b]:
        count += mid - a
    merged.append(nums[b])
    b += 1
```
Fix
```
j = mid
for i in range(lo, mid):
    while j < hi and nums[i] > 2 * nums[j]:
        j += 1
    count += j - mid
```
What happens: The merge moves a and b by the test nums[a] <= nums[b]. The pair test is a different one, nums[i] > 2 * nums[j]. So the merge can move past a right value before it is tested against the larger left values. The separate pass tests every left value with its own pointer j.
Example: nums = [3, 5, 2, 1]
Mistake: returns 2Fix: returns 3
Gotcha 2: Calling sort_count(lo, mid + 1) with an exclusive hi
Mistake
```
count = sort_count(lo, mid + 1) + sort_count(mid, hi)
```
Fix
```
count = sort_count(lo, mid) + sort_count(mid, hi)
```
What happens: hi is exclusive, so sort_count(lo, mid) already covers the left half. Take a range of two values, lo and lo + 2. Then mid is lo + 1, and sort_count(lo, mid + 1) calls the same range again. The calls repeat until Python raises a RecursionError.
Example: nums = [2, 1]
Mistake: raises RecursionErrorFix: returns 0
Gotcha 3: Resetting j = mid for every i
Mistake
```
for i in range(lo, mid):
    j = mid
```
Fix
```
j = mid
for i in range(lo, mid):
```
What happens: The answer stays correct. But j then walks the right half again for every left value. Each merge step becomes quadratic, and the whole sort is O(N^2). The left half is sorted, so the right values that pair with nums[i] also pair with every later nums[i]. Keep j where it stopped.
Gotcha 4: Testing nums[i] >= 2 * nums[j]
Mistake
```
while j < hi and nums[i] >= 2 * nums[j]:
```
Fix
```
while j < hi and nums[i] > 2 * nums[j]:
```
What happens: Reverse Pairs (LC 493) needs nums[i] to be strictly greater than 2 * nums[j]. With >=, a pair where nums[i] equals 2 * nums[j] is counted too.
Example: nums = [2, 1]
Mistake: returns 1Fix: returns 0
Gotcha 5: Halving with nums[i] // 2 > nums[j]
Mistake
```
while j < hi and nums[i] // 2 > nums[j]:
```
Fix
```
while j < hi and nums[i] > 2 * nums[j]:
```
What happens: // rounds down. For an odd nums[i], such as 7, 7 // 2 is 3, and the pair 7 and 3 is missed. 7 > 2 * 3 is True, so it is a pair. Python never overflows on 2 * nums[j]. In Java or C++, compute it in 64 bits instead of halving.
Example: nums = [7, 3]
Mistake: returns 0Fix: returns 1

Canonical LeetCode:Reverse Pairs (LC 493)Count of Smaller Numbers After Self (LC 315)Count of Range Sum (LC 327)Number of Pairs Satisfying Inequality (LC 2426)Create Sorted Array through Instructions (LC 1649)

Open the Merge Sort Counting card

8Segment Tree

array ➔ binary tree of range sums ➔ O(log N) point update & range sum

Segment Tree (Range Sums With Point Updates)

Spot it when: The array changes one element at a time, and between the changes you must report the sum of any stretch of elements, as in Range Sum Query - Mutable (LC 307). The same tree can also store a maximum or a minimum of each range, which a Fenwick tree cannot.

Mode 8 · Segment Tree

Python

1	class SegmentTree:
2	"""Sum Segment Tree with Point Updates.
3	Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half).
4	Time: O(N) build, O(log N) query & update \| Space: O(N)
5	"""
6	def __init__(self, nums: list[int]) -> None:
7	self.n = len(nums)
8	self.tree = [0] * (4 * self.n) # tree[node] is the sum of the slots node covers; 4n is always enough room
9	self._build(nums, 0, 0, self.n - 1)
10
11	def _build(self, nums: list[int], node: int, left: int, right: int) -> None:
12	# 1. Fill A Leaf With Its One Element, Else Build Both Halves First:
13	# A node's sum is the sum of its two halves, so both children must be built before this node can combine them.
14	if left == right:
15	self.tree[node] = nums[left] # Leaf: one array element
16	return
17	mid = (left + right) // 2
18	self._build(nums, 2 * node + 1, left, mid)
19	self._build(nums, 2 * node + 2, mid + 1, right)
20	self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Combine the two halves
21
22	def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None:
23	# 1. Default The Range, Then Stop At The Leaf For index:
24	# The first call omits left/right, so they default here; once left == right only one
25	# slot is left in the range, and that slot is index, so the leaf's own value is set.
26	if right == -1:
27	right = self.n - 1 # Default: start at the whole range
28	if left == right:
29	self.tree[node] = val # Reached the leaf for index
30	return
31
32	# 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up:
33	# index lies in exactly one half, so only one child is visited; recomputing this node's
34	# sum from both children afterward keeps every ancestor's stored sum in sync with the new leaf.
35	mid = (left + right) // 2
36	if index <= mid:
37	self.update(index, val, 2 * node + 1, left, mid) # Go left
38	else:
39	self.update(index, val, 2 * node + 2, mid + 1, right) # Go right
40	self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Recompute on the way up
41
42	def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int:
43	# 1. Default The Range, Then Resolve Full Overlap Or No Overlap:
44	# A node fully inside [ql, qr] can answer from its own stored sum; a node fully outside
45	# contributes 0, since it holds none of the requested slots.
46	if right == -1:
47	right = self.n - 1
48	if ql <= left and right <= qr:
49	return self.tree[node] # Fully inside the query: use the stored sum
50	if right < ql or left > qr:
51	return 0 # Fully outside: contributes nothing
52
53	# 2. Split On Partial Overlap And Add Both Halves:
54	# Neither child's range is fully inside or outside, so both are queried and their sums are added.
55	mid = (left + right) // 2 # Partial overlap: split into both halves
56	return (self.query(ql, qr, 2 * node + 1, left, mid) +
57	self.query(ql, qr, 2 * node + 2, mid + 1, right))
58
59
60	class NumArray:
61	"""Range Sum Query - Mutable: every call goes straight to the segment tree."""
62	def __init__(self, nums: list[int]):
63	self.seg = SegmentTree(nums)
64
65	def update(self, index: int, val: int) -> None:
66	self.seg.update(index, val) # The leaf is overwritten with val, then its ancestors recomputed
67
68	def sumRange(self, left: int, right: int) -> int:
69	return self.seg.query(left, right)

Node node stores the sum of the slots left..right it covers, and its children 2 * node + 1 and 2 * node + 2 store the sums of the two halves. So update sets one leaf and, on the way back up, rebuilds each ancestor's sum from its two children. query(ql, qr) splits the range the same way: a node fully inside [ql, qr] returns its stored self.tree[node], a node fully outside returns 0, and a node that overlaps only part of the range adds the answers of both children. At most two nodes per level overlap only part of the range, so every update and query stays on a few nodes per level. The trap is the last line of update, self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]. If it is missing, the leaf changes but every ancestor keeps its old sum, and a later query that returns a stored self.tree[node] reads that old sum.

Gotchas1 of 5

The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistake
```
else:
    self.update(index, val, 2 * node + 2, mid + 1, right)
```
Fix
```
else:
    self.update(index, val, 2 * node + 2, mid + 1, right)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
```
What happens: update changes the leaf for index, then returns up the recursion. Each node on the way holds the sum of its range. Without the line self.tree[node] = ..., those nodes keep their old sum. A later query that fully covers such a node returns its stored self.tree[node] and misses the new value. For nums = [1, 3, 5], the root keeps 9 after update(1, 2), although the sum is now 8.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 9Fix: returns 8
Gotcha 2: Using a stored sum when the node only overlaps the query
Mistake
```
if left <= qr and ql <= right:
```
Fix
```
if ql <= left and right <= qr:
```
What happens: self.tree[node] is the sum of every slot the node covers. A node that only overlaps [ql, qr] also covers slots outside it. With the overlap test, query returns that whole sum and never asks the two children. The extra slots are counted in the answer. The correct test returns the stored sum only when the node lies inside [ql, qr].
Example: nums = [1, 3, 5], then sumRange(0, 1)
Mistake: returns 9Fix: returns 4
Gotcha 3: Adding val to the leaf instead of setting it
Mistake
```
self.tree[node] += val
```
Fix
```
self.tree[node] = val
```
What happens: LeetCode's update(index, val) replaces nums[index] with val. This tree stores the slot values themselves in its leaves, so the leaf must be set to val. With +=, the leaf holds the old value plus val. A Fenwick tree is different: it only adds, so it receives the change val - old.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 11Fix: returns 8
Gotcha 4: Allocating 2 * n nodes instead of 4 * n
Mistake
```
self.tree = [0] * (2 * self.n)
```
Fix
```
self.tree = [0] * (4 * self.n)
```
What happens: With children at 2 * node + 1 and 2 * node + 2, the tree has gaps when n is not a power of two. Some nodes then get an index of 2 * n or more. With only 2 * n slots, _build raises IndexError when it reaches such a node. 4 * n slots are always enough.
Example: nums = [1, 2, 3, 4, 5, 6], then sumRange(0, 5)
Mistake: raises IndexErrorFix: returns 21
Gotcha 5: Updating a whole range one element at a time
What happens: This tree changes one position per update, in O(log N) time. Changing every value in a range this way costs O(log N) for each element of the range. For many range updates, use lazy propagation. It stores a pending change at a node and passes it to the children only when a query or update goes below that node.

Canonical LeetCode:Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)Count of Range Sum (LC 327)Reverse Pairs (LC 493)

Open the Segment Tree card

Built on the mental models above

Max Segment TreeMax Segment Tree (Range Maximum Query)
Each node keeps the maximum instead of the sum, so an update writes max(...) and a query takes max over the covered nodes.

The Advanced Data Structures Decision Rule

When facing an unseen system design or data structure problem, ask in this order:

Step 1.Does the problem involve prefix matching, autocomplete, or multi-word grid search?

➔ Trie

Implement Trie (Prefix Tree) (LC 208)Design Add and Search Words Data Structure (LC 211)

Build Trie and descend character by character in O(L) time.

Step 2.Does the problem group elements into dynamic connected components or detect undirected cycles?

➔ Union-Find

Redundant Connection (LC 684)Number of Provinces (LC 547)

Maintain parent and rank arrays in O(alpha(N)).

Step 3.Does the problem require frequent point updates and prefix sum range queries?

➔ Fenwick Tree

Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)

Implement 1-indexed BIT using lowbit = i & -i.

Step 4.Do range queries mix with updates, where each tree node must store a range sum, or something a Fenwick tree can't do easily (range max or min, a change to a whole range)?

➔ Segment Tree

Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)

Each node stores its segment's aggregate (here the sum of its slots); updates and queries touch O(log N) nodes, with lazy tags for range updates.

Step 5.Does each step need the largest value in a window of slots, and then a change at one slot?

➔ Max Segment Tree

Longest Increasing Subsequence II (LC 2407)Fruits Into Baskets III (LC 3479)

Store the maximum in every node of a segment tree; an update recomputes the maximum of each ancestor, and a query takes the maximum over the covered nodes.

Step 6.While inserting keys, do you need the closest key at or above (or at or below) a value?

➔ Ordered Set

My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)

Keep the keys sorted (SortedList) and bisect for the floor and the ceiling in O(log N).

Step 7.Does the problem require O(1) key-value lookup with recency eviction?

➔ LRU Cache

LRU Cache (LC 146)LFU Cache (LC 460)

Pair a Hash Map with a Doubly-Linked List with sentinel head/tail.

Step 8.Must a set support insert, remove and a uniform random pick, each in O(1) on average?

➔ Insert Delete GetRandom

Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Store values in a list plus a value-to-index map; remove by moving the last value into the gap and popping.

Step 9.Must you count the pairs of positions (i < j) whose values are in a given order, or differ by more than a limit, without checking every pair?

➔ Merge Sort Counting

Reverse Pairs (LC 493)Count of Smaller Numbers After Self (LC 315)

Sort with merge sort, and count the pairs between the two sorted halves just before each merge, in O(N log N).

Pattern Architecture & Invariant Design Masterclass

This pattern is different from the others in the curriculum. It is not a way of walking data — it is a pair of purpose-built containers you construct when the plain ones cannot answer the question fast enough. The skill being tested is recognising which query shape demands which structure, and being able to build it from nothing.

A Trie (prefix tree) stores words as paths down a tree, one character per edge. Every word sharing a prefix shares that part of the path. Looking up a word costs time proportional to the length of the word — completely independent of how many words are stored. A million words or ten, "apple" takes five steps.

The one subtlety, and it is the whole interview question: a path existing does not mean a word was stored. After inserting "apple", the path for "app" exists — it is a stretch of "apple"'s path. Every node therefore needs a boolean flag marking "a word ends exactly here." Searching checks the flag; prefix-matching does not. Getting that distinction wrong is the classic Trie bug.

Union-Find (Disjoint Set Union) answers one question fast: "are these two things in the same group?" — while groups keep merging. Each element points at a parent; following parents leads to a group's representative. Two elements are in the same group when they reach the same representative. Merging two groups is one pointer change.

The one subtlety: naively, the parent chains grow into long lists and every query walks them, degrading to O(n). Two small fixes — path compression (re-point every node you pass directly at the root) and union by size (always hang the smaller tree under the larger) — make every operation effectively constant time.

🔬 Variable Anatomy: The 7 Variables Every Trie & Union-Find Uses

To connect abstract specialized tree structures with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

# =============================================================================
# 1. TRIE MASTER STRUCTURE
# =============================================================================
class TrieNode:
    def __init__(self):
        self.children = {}       # 🔤 Outgoing Character Edges: char -> TrieNode
        self.is_end = False      # 🚩 Terminal Word Flag: True ONLY on final char of stored word
 
class TrieMasterTemplate:
    def __init__(self):
        self.root = TrieNode()   # ⚓ Empty Prefix Root Anchor
 
    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_end = True       # ⚠️ Set True strictly on the terminal node
 
    def search(self, word: str) -> bool:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.is_end       # ⚠️ Requires is_end == True
 
    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True              # ⚠️ Prefix existence is sufficient
 
 
# =============================================================================
# 2. DISJOINT SET UNION (UNION-FIND) MASTER STRUCTURE
# =============================================================================
class UnionFindMasterTemplate:
    def __init__(self, size: int):
        self.parent = list(range(size))  # 🔗 Representative Parent Pointers
        self.rank = [1] * size           # 🌲 Component Tree Size / Rank
        self.num_components = size       # 🔢 Total Disjoint Components
 
    def find(self, x: int) -> int:
        # Path Compression: flatten traversal path directly to root
        root = x
        while root != self.parent[root]:
            root = self.parent[root]
        
        curr = x
        while curr != root:
            nxt = self.parent[curr]
            self.parent[curr] = root     # ⚡ Point directly to canonical root
            curr = nxt
        return root
 
    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # 🚫 Already connected (Cycle detected!)
 
        # Union by Rank / Size: hang smaller tree under larger root
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.rank[ra] += self.rank[rb]
        self.num_components -= 1
        return True

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`root`	`TrieNode` anchor	"Where does prefix exploration begin?"	❌ Storing characters on root confuses empty prefix `""` with 1-character words.
`children`	`dict[str, TrieNode]`	"Does an edge exist for the next character in this prefix?"	❌ Using fixed 26-element arrays crashes on uppercase or non-ASCII characters without index mapping.
`is_end`	Boolean flag	"Did a stored word terminate at this node, or is it merely a prefix?"	❌ If `search` returns `True` without checking `is_end`, `search("app")` returns `True` after only inserting `"apple"`.
`parent`	`list[int]`	"Who is the immediate ancestor / canonical representative of node $x$ ?"	❌ Comparing `parent[a] == parent[b]` instead of `find(a) == find(b)` fails on deep unflattened trees.
`rank` / `size`	`list[int]`	"Which tree has larger depth/size to serve as root during union?"	❌ Without union-by-rank, parent chains degenerate into $O(N)$ linked lists.
`num_components`	Integer count	"How many independent connected clusters remain after dynamic edges?"	❌ Without decrementing on valid unions, calculating active components requires an $O(N)$ scan.
`lowbit`	`i & (-i)`	"What is the step size for Fenwick tree navigation?"	❌ In Binary Indexed Trees, calculating lowbit without two's complement requires loop searches.

🧠 The Universal Contracts of Advanced Containers:

Trie Invariant: Word length $L$ , not dataset size $N$ , dictates latency. Insertion and search are strictly $O(L)$ .

Union-Find Invariant: With both Path Compression and Union-by-Rank, the amortized cost per operation is $O(\alpha(N))$ (inverse Ackermann function $\le 4$ for all physical universe inputs).

🌟 The 3 Dimensions of Advanced Data Structures & Structural Invariants

Every Advanced Data Structure is governed by 3 Key Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                 THE 3 DIMENSIONS OF ADVANCED DATA STRUCTURES                │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. TARGET DOMAIN  │ Character paths (Trie) vs         │ "Are we indexing    │
│    SPECIALIZATION │ Equivalence partitions (DSU)      │ prefixes or sets?"  │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. LATENCY BOUND  │ O(L) per word (Trie) vs           │ "How does runtime   │
│    INVARIANT      │ O(alpha(N)) amortized (DSU)       │ scale with input?"  │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. STRUCTURAL     │ Node flag separation (`is_end`) vs│ "How do we compress │
│    COMPRESSION    │ In-place pointer flattening       │ path traversal?"    │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: Prefix Searching & Autocomplete (Trie)

When querying millions of words for common prefixes, hashing every prefix consumes $O(N \cdot L^2)$ memory.
The Rule: Build a 26-ary character tree. Descend one character edge per step. Prefix lookup stops when characters survive; word search requires curr.is_end == True.
The Result: $O(L)$ exact and prefix searches independent of dictionary volume.

🔵 Scenario B: Dynamic Connectivity & Undirected Cycle Detection (Union-Find)

When edges arrive incrementally in a graph, running DFS/BFS to check connectivity after each edge takes $O(E \cdot (V + E))$ .
The Rule: Initialize parent[i] = i. For edge $(u, v)$ , compute ra, rb = find(u), find(v). If ra == rb, a cycle exists! Otherwise merge with union(u, v).
The Result: Near-instant $O(\alpha(N))$ connectivity verification per edge.

💡 The Ultimate Takeaway Decision Rule:
When analyzing an unseen data structure problem, ask: "Is this a string prefix problem, or an incremental set-merging problem?"

If Prefix matching / Autocomplete / Word Boggle ➔ Build a Trie ( $O(L)$ query).

If Dynamic connected components / Redundant connections ➔ Build Union-Find with Path Compression ( $O(\alpha(N))$ ).

If Frequent prefix sum point updates ➔ Build a Fenwick Tree / BIT ( $O(\log N)$ ).

🎯 The 5 Essential Advanced Data Structures Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                               THE 5 CORE ADVANCED DATA STRUCTURE ARCHETYPES                                      │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Container Mechanism  │ Invariant / Structural Rule   │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. Trie Prefix Tree    │ 26-ary character tree│ `is_end` required for search; │ Implement Trie (LC 208), Add &   │
│    (LC 208 / LC 211)   │ with `is_end` flag   │ prefix only checks traversal  │ Search Words (LC 211) — O(L)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Trie + 2D Matrix    │ Trie coupled with    │ Prune grid branches when Trie │ Word Search II (LC 212) —        │
│    (LC 212)            │ in-place DFS marking │ node child is missing         │ O(R * C * 4^L) with fast pruning │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. DSU Cycle Detection │ Disjoint Set Union   │ Edge redundant iff roots match│ Redundant Connection (LC 684) —  │
│    (LC 684 / LC 547)   │ with Path Compression│ `find(u) == find(v)`          │ O(E * alpha(V))                  │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Equivalence Sets    │ DSU on mapped indices│ Connect distinct attributes to│ Accounts Merge (LC 721), Min     │
│    (LC 721 / LC 1584)  │ (email -> account id)│ single representative owner   │ Cost Connect Points (LC 1584)    │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 5. Fenwick Tree / BIT  │ 1-indexed array with │ `lowbit = i & -i` steps parent│ Range Sum Query Mutable (LC 307) │
│    (LC 307 / LC 315)   │ lowbit index jumps   │ prefix sums and point updates │ — O(log N) update and query      │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

🌲 1. Trie: Word Insertion and Verification (LC 208)

Mental Model: A Trie routes character sequences down shared trunk prefixes.
Code Blueprint:

Code / Blueprint

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def _walk(self, s: str):
        curr = self.root
        for ch in s:
            if ch not in curr.children:
                return None
            curr = curr.children[ch]
        return curr
 
    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_end = True
 
    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end
 
    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

🔍 2. Trie + 2D Matrix Search (LC 212 — Word Search II)

Mental Model: Loading words into a Trie allows exploring a 2D board once while searching for thousands of dictionary words simultaneously.
Pruning Invariant: If the current grid path character does not exist in the active Trie node's children, backtrack immediately without exploring 4-way neighbors.

🔗 3. Union-Find: Cycle Detection in Redundant Connections (LC 684)

Mental Model: Two vertices $u$ and $v$ are already connected if they share the same representative. An extra edge between them creates an undirected cycle.
Code Blueprint:

Code / Blueprint

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = list(range(n + 1))
    rank = [1] * (n + 1)
 
    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]
 
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]  # Cycle detected!
        # Union-by-rank: attach shallower tree under deeper tree
        if rank[ru] < rank[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        if rank[ru] == rank[rv]:
            rank[ru] += 1
    return []

📧 4. Equivalence Grouping (LC 721 — Accounts Merge)

Mental Model: Map every unique email to an integer identifier, union emails belonging to the same user account, and group all emails sharing the same root representative.

📈 5. Binary Indexed Tree / Fenwick Tree (LC 307)

Mental Model: Uses the binary representation of integers to store cumulative frequency intervals, enabling point updates and prefix sums in $O(\log N)$ time.

🌳 Evaluating Trie and DSU State & Space Invariants

Designing advanced custom containers requires understanding memory and pointer structures:

1. Trie Node Space vs Dictionary Allocations

Python dictionaries (children = {}) dynamically allocate space only for edges that exist, which is much more memory efficient than pre-allocating size-26 lists on sparse alphabets.
To prevent memory leaks in large grid searches, prune leaf nodes from the Trie when their words are found.

2. Union-Find 1-Indexing and Iterative Traversal

Many graph problems use 1-indexed vertex IDs. Always allocate parent = list(range(n + 1)) to avoid index out-of-range errors.
Prefer iterative path compression or single-pass path splitting over deep recursive find() calls on long degenerate chains.

💡 Staff SWE Architectural Invariant:
Choose Trie when the query space is bounded by character prefix lengths ( $O(L)$ ), and choose Disjoint Set Union when the problem involves dynamic equivalence clustering or cycle detection in undirected graphs ( $O(\alpha(N))$ ).

Understanding Invariants: Prefix Tree Termination & Disjoint Set Path Compression

A Trie node's is_end flag, not its path existence, determines if a word was stored. In Union-Find, two elements are connected if and only if find(a) == find(b).

Trie nodes encode shared prefixes along paths down a tree; Union-Find flattens parent pointers on traversal via path compression and balances heights with union-by-rank to achieve near O(1) amortized operations.

Trie Terminal Word vs Prefix Invariant

Condition: In search(word), after consuming all characters, check curr.is_end

Action: return curr.is_end for exact word search, return True for startsWith(prefix)

A prefix path exists for any substring of an inserted word, but is_end == True only for words explicitly added.

Disjoint Set Union Cycle Detection Invariant

Condition: If find(u) == find(v) when processing an undirected edge (u, v)

Action: return False (union fails) and flag edge as a redundant cycle

Adding an edge between two vertices that already share the same canonical representative creates a cycle.

Common Questions

"If I can walk the whole word without falling off the Trie, doesn't that mean the word must be stored? Why do we need a separate is_end flag at all?"

Because a path existing and a word being stored are two different facts, and a Trie's whole efficiency comes from sharing paths between words that were never themselves inserted.

Trace it concretely: insert only "apple" into an empty Trie. The path a → p → p → l → e now exists. But the path a → p → p — spelling "app" — also exists, purely as a byproduct of walking through "apple"'s own path. If search("app") reused the "did I fall off the tree" test that startsWith correctly uses, it would answer True for "app", even though "app" was never inserted on its own.

The only fact that distinguishes "this node happens to lie on someone else's path" from "a word was deliberately stored ending exactly here" is a flag set at insert-time on that exact node, and checked at query-time on that exact node — nothing about the tree's shape encodes it, because sharing that shape between related words is the entire reason a Trie is cheap in the first place. That's why search is path exists AND is_end, while startsWith is path exists alone: startsWith("app") is legitimately asking "is there anything below this point," which mere path existence answers correctly, while search("app") asks the strictly stronger question "does a word end at this exact point," which only the flag can answer.

Coach discussion points

1.
"I inserted only 'apple'. Tell me what search('app') and startsWith('app') return, and explain why they differ when they walk to the same node." — The single highest-signal Trie question. A student who has genuinely built one answers instantly; one who has copied a template hesitates.
2.
"When is a hash set better than your Trie, and when is it useless?" — Tests whether the structure was chosen or reached for. The honest answer names the prefix query as the dividing line, and the construction cost as the price.
3.
"You wrote path compression. Suppose I delete it — what still works, and what stops working?" — Everything still works; it just gets slow, and only on large inputs. Distinguishing correctness bugs from performance bugs is a genuinely senior skill.
4.
"Your union returns False sometimes. What does the caller do with that, and what other problem does it solve?" — Cycle detection. Follow-up: "could you use this on a directed graph?" — No, and knowing why (DSU has no notion of edge direction) is the boundary-of-the-tool signal.
5.
"In Number of Islands II, why does a successful union() decrement the count, when in Redundant Connection a successful cycle check is union() returning False?" — Because the two problems ask opposite questions of the same primitive: Redundant Connection asks "did this edge create a redundant connection?" (answered by union() returning False), while Number of Islands II asks "did this operation productively merge two components?" (answered by union() returning True). A student who can articulate this duality has genuinely internalized DSU rather than memorized two separate templates.
6.
"Why can't you just reuse your LRU Cache's hash map + doubly-linked list for LFU, adding a freq field to each node?" — Because a single linked list can only maintain one total order. The moment two keys have different frequencies but you need both "which frequency is lowest" and "which key is oldest within that frequency," one list can't express two independent orderings at once. That's exactly why LFU needs a second hash map (freq -> bucket), not just an extra field.
7.
"Your min_freq pointer only ever increments, never decrements after a get. Walk me through exactly when it does change, and prove it's never stale." — It changes only when the bucket it currently points at becomes empty (advances by exactly 1, since frequencies increase by exactly 1 per access) or when a brand-new key is inserted (reset to 1, since a fresh key is trivially the new minimum). Proving it's never stale means showing no other code path can leave min_freq pointing at a bucket that no longer exists.
8.
**"All Oone needs both a max and a min in O(1). Why doesn't LFU Cache need the same trick for its min_freq-- couldn't you also track amax_freq?"** — LFU never needs the max frequency for anything; it only ever evicts from the min. Tracking a max_freq` you never read would be a real correctness liability (another pointer to keep consistent) for zero benefit -- a good check for whether a student is pattern-matching the bucket trick or actually reasoning about what each structure is asked to report.

Complexity analysis

Trie

Operation	Time	Why
`insert(word)`	`O(L)`	One dictionary lookup or insertion per character, each `O(1)`
`search(word)`	`O(L)`	Same walk, plus one flag read
`startsWith(prefix)`	`O(L)`	Same walk, no flag read

L is the length of the query, not the size of the stored set. That is the entire selling point: with a million words stored, search("cat") still takes three steps. Compare with a hash set, which also does O(L) membership (it must hash the whole string) but cannot answer startsWith at all without scanning every key. The prefix query is the reason to pay for a Trie.

Space: O(total characters inserted) in the worst case. With 26 possible children per node, a naive fixed-array implementation costs 26 pointers per node whether used or not; a dictionary costs only what is present. For a dictionary of English words the sharing is substantial — "car", "card", "care", "careful" occupy 10 nodes, not 18.

Union-Find

Operation	Time	Why
`find(x)`	`O(α(n))` amortised	With path compression and union by size
`union(a, b)`	`O(α(n))` amortised	Two finds plus one pointer write
Space	`O(n)`	Two integer arrays

α(n) is the inverse Ackermann function. It grows so slowly that for any n that could physically be stored — beyond the number of atoms in the observable universe — α(n) < 5. Treat it as constant, but be able to say what it is, because "effectively O(1), formally O(α(n)) inverse Ackermann" is a precise answer and "O(1)" alone is a hand-wave.

What happens without the optimisations, stated exactly:

Neither optimisation: O(n) per operation — the structure degenerates into a linked list.
Path compression only: O(log n) amortised.
Union by size only: O(log n).
Both: O(α(n)). The near-constant bound needs both, and knowing that is the follow-up question.

LRU Cache

Operation	Time	Why
`get(key)`	`O(1)` average	Hash map pointer lookup + fixed-cost doubly-linked-list splice
`put(key, value)`	`O(1)` average	Hash map insertion + fixed-cost splice + at most one fixed-cost eviction
Space	`O(C)`	Hash map of size `C` + doubly linked list of `C + 2` nodes (`C` = capacity)

LFU Cache

Operation	Time	Why
`get(key)`	`O(1)` average	`key_node` lookup + `_bump_freq`'s fixed-cost bucket splice
`put(key, value)`	`O(1)` average	`key_node`/`freq_bucket` lookups + fixed-cost splice + at most one fixed-cost eviction
Space	`O(C)`	`key_node` map of size `C` + `freq_bucket` map whose bucket node counts sum to `C` (`C` = capacity)

min_freq never costs anything extra: it is only ever read, or bumped by exactly 1 when its own bucket empties, or reset to 1 on a fresh insert -- it is never recomputed by scanning all buckets, which is the detail that keeps this genuinely O(1) rather than O(1) amortised against an occasional scan.

All O`one Data Structure

Operation	Time	Why
`inc(key)` / `dec(key)`	`O(1)` average	`key_bucket` lookup + `_insert_after`'s fixed-cost reuse-or-splice + fixed-cost set add/remove
`getMaxKey()` / `getMinKey()`	`O(1)`	Direct peek at `tail.prev`/`head.next`'s key set, no traversal
Space	`O(K)`	`key_bucket` map of size `K` + bucket chain whose key sets sum to `K` (`K` = number of distinct keys currently tracked)

Production Systems Deployment & Motivation

Trie: a search box suggests completions after every keystroke. It cannot scan a million-word dictionary between keys. It walks one edge per character down a prefix tree and reads off the words hanging below — the cost depends on what you typed, never on the dictionary's size. This is what powers autocomplete, IDE symbol lookup, IP routing tables, and spell-checkers.

Union-Find: a network is being built one cable at a time, and after each cable an operator must know whether two machines can now reach each other, and whether the new cable created a redundant loop. Rerunning a traversal after every cable is O(V + E) each time; Union-Find answers each question in effectively constant time. Kruskal's minimum-spanning-tree algorithm, image segmentation, and cycle detection in incremental graphs all use it.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if Trie pointers or Disjoint Set Union structures feel abstract right now! Advanced data structures compress large domains into efficient navigation trees and dynamic equivalence partitions. As you progress through the Archetype Variants (from Implement Trie and Word Search II to Union-Find Cycle Detection and Accounts Merge), each hands-on challenge will cement this intuition until implementing find() with path compression and Trie node lookups becomes second nature.

Conflating path existence with word completion: search must verify node.is_end == True. Checking only that the character chain exists causes prefix-only matches (e.g. searching 'app' when only 'apple' was inserted) to incorrectly return True.
Omitting path compression (Union-Find). Every test with 10 elements passes; the one with 100,000 times out. The most common performance failure in this pattern.
Using a singly-linked list (LRU Cache). Removing a node needs its prev pointer; without one, removal degrades to O(N). This is the whole reason the structure is doubly linked.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "autocomplete prefix matching", "dynamic connected components with fast merges", "constant-time key-value eviction (LRU/LFU)", "prefix search across dictionary". Standard hash maps and arrays cannot satisfy prefix branching or dynamic equivalence partitions in sub-linear time.

CONSTRAINTS & BOUNDS

Queries up to $10^5$ , dictionary words up to $10^5$ of length $L$ . Disjoint Set Union (DSU) operates in near-constant $O(\alpha(N))$ amortized time. Trie prefix searches run in strictly $O(L)$ time independent of dictionary size $N$ .

FAANG PRODUCTION TRAPS & EDGE CASES

Pointer overhead and memory bloat in naive Tries (each node allocating 26 child pointers on heap); forgetting path compression in DSU ( $O(\alpha(N))$ degrades to $O(N)$ worst-case tree); DLL node dangling pointers on LRU eviction.

Theory Context•Advanced Data Structures

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Prefix Trees (Tries): Exploit common character subpaths to guarantee string insertion, exact search, and prefix validation in $O(L)$ time proportional strictly to string length, independent of dictionary size.
Disjoint Set Union (DSU / Union-Find): Tracks dynamic equivalence classes and connected components in near-constant $O(\alpha(N))$ amortized time using tree flattening (path compression) and tree balancing (union-by-rank).
Composite Caches (LRU, LFU, All O`one): Couples hash maps with doubly-linked lists and frequency buckets to deliver simultaneous $O(1)$ key lookup and $O(1)$ ordered eviction.

🏙️ The Analogy: The Metropolitan Public Transit & Archive System

Think of a city infrastructure system:

A Trie is the city's postal routing hub: letters destined for "101 Main St", "101 Market St", and "101 Michigan Ave" all travel down the exact same highway corridor ("101 M...") before branching off at the final block. Words with a shared prefix share the same path.
Union-Find is the regional marriage and civil registry: instead of asking every person if they are related to someone else by tracing an entire family tree, every person simply names their community's recognized village elder (canonical root). If two people name the same elder, they belong to the same clan.
LRU/LFU Caches are the tiered express warehouses: an inventory clipboard (hash map) tells the forklift driver the exact shelf coordinates of any pallet, while a physical conveyor belt (doubly linked list) automatically moves accessed items to the front and pushes dusty, untouched pallets toward the donation chute at the back.

🔑 Why It Works

Each paradigm couples an $O(1)$ entry map with an localized structural invariant, bypassing $O(N)$ brute-force scans.

Visual Blueprint & State Transition Model

Core Invariant Specification

Boundary Model: Trie Prefix Tree Branching / DSU Near-Flat Forest

Trie: root-to-node path encodes common prefix; DSU: find(u) with path compression flattens tree so root is direct parent.

Loop Invariant Termination

Trie: traverse word char-by-char in O(L); DSU: if find(u) != find(v): union(u, v) in O(alpha(N)).

The 8 Mental Models of Advanced Data Structures

Select the specialized data structure based on query semantics.

1Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Trie (Prefix Tree)

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Mode 1 · Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Open the Trie card

2Union-Find

dynamic edges / sets ➔ find canonical root ➔ flatten tree & merge ranks

Union-Find (Disjoint Set Union)

Spot it when: Items join groups over time, and you ask whether two are connected, how many groups there are, or which edge first closes a cycle.

Mode 2 · Union-Find

Python

1	from typing import List
2
3	class UnionFind:
4	"""Union-Find with path compression and union by size, run on Redundant Connection.
5	Time: O(N · alpha(N)) for N edges, O(alpha(N)) amortized per call \| Space: O(N)
6	"""
7	def __init__(self, n: int):
8	self.parent = list(range(n))
9	self.size = [1] * n
10	self.num_components = n
11
12	def find(self, x: int) -> int:
13	"""Path compression: points traversed nodes directly to root."""
14	root = x
15
16	# 1. Walk Up To The Root:
17	# parent[root] == root only at the root, so climbing parent links from x always ends there.
18	while root != self.parent[root]:
19	root = self.parent[root]
20
21	# 2. Compress The Path:
22	# Repointing every visited node straight at root shortens the next walk from any of them to one step.
23	while x != root:
24	nxt = self.parent[x]
25	self.parent[x] = root
26	x = nxt
27
28	return root
29
30	def union(self, a: int, b: int) -> bool:
31	"""Union by size: hangs smaller tree under larger."""
32	ra, rb = self.find(a), self.find(b)
33
34	# 1. Detect An Already-Closed Group:
35	# Equal roots mean a and b were already connected before this edge, so this edge closes a cycle.
36	if ra == rb:
37	return False # Already connected / cycle detected!
38
39	# 2. Hang The Smaller Tree Under The Larger:
40	# Attaching the smaller tree to the larger root keeps every tree's height small, which keeps find's walk short.
41	if self.size[ra] < self.size[rb]:
42	ra, rb = rb, ra
43
44	self.parent[rb] = ra
45	self.size[ra] += self.size[rb]
46	self.num_components -= 1
47	return True
48
49	def findRedundantConnection(edges: List[List[int]]) -> List[int]:
50	uf = UnionFind(len(edges) + 1) # Nodes are numbered 1..n
51
52	# 1. Union Each Edge, Stopping At The First Cycle:
53	# union returns False only when its two endpoints are already in the same group, which is exactly the edge that closes the first cycle.
54	for a, b in edges:
55	if not uf.union(a, b):
56	return [a, b] # a and b were already connected: this edge closes the cycle
57	return []

Gotchas1 of 4

The trap
Gotcha 1: Writing self.parent[b] = a instead of linking the roots
Mistake
```
self.parent[b] = a
```
Fix
```
self.parent[rb] = ra
```
What happens: b may not be a root. Then self.parent[b] = a moves only b into the other group. The rest of b's old group still points at its old root. A later union of the two groups finds two different roots and returns True. So the edge that closes the cycle is missed.
Example: edges = [[1, 2], [3, 2], [1, 3]]
Mistake: returns []Fix: returns [1, 3]
Gotcha 2: Creating UnionFind(len(edges)) for nodes numbered 1 to n
Mistake
```
uf = UnionFind(len(edges))
```
Fix
```
uf = UnionFind(len(edges) + 1)
```
What happens: Redundant Connection (LC 684) numbers its nodes from 1 to n, and n equals len(edges). UnionFind(len(edges)) creates slots 0 to n - 1 only. The first edge that touches node n raises IndexError.
Example: edges = [[1, 2], [1, 3], [2, 3]]
Mistake: raises IndexErrorFix: returns [2, 3]
Gotcha 3: Passing items that are not small integers to union
Mistake
```
uf.union("a@x.com", "b@x.com")
```
Fix
```
ids = {email: i for i, email in enumerate(emails)}
uf.union(ids["a@x.com"], ids["b@x.com"])
```
What happens: self.parent is a list, so find needs an integer index from 0 to n - 1. An email address or a coordinate pair raises TypeError. Give every item an integer id first, or keep parent in a dict.
Example: emails = ["a@x.com", "b@x.com", "c@x.com"]
Mistake: raises TypeErrorFix: returns True
Gotcha 4: Using union-find to find a cycle in a directed graph
Mistake
```
has_cycle = findRedundantConnection(edges) != []
```
Fix
```
has_cycle = has_directed_cycle(edges)  # Kahn's topological sort
```
What happens: Union-find ignores the direction of an edge. The edges 1 -> 2, 1 -> 3 and 2 -> 3 have no directed cycle. Union-find still joins 2 and 3 through 1, so it reports a cycle at 2 -> 3. Use a DFS with three colours or a topological sort instead, as in Course Schedule (LC 207).
Example: directed edges = [[1, 2], [1, 3], [2, 3]]
Mistake: returns TrueFix: returns False

Open the Union-Find card

3LRU Cache

key-value storage ➔ hash map (O(1) lookup) + DLL (O(1) recency)

LRU Cache (HashMap + Doubly Linked List)

Spot it when: A design problem asks for O(1) lookups plus eviction by least recent use (or by frequency).

Mode 3 · LRU Cache

Python

1	from typing import Optional
2
3	class DLinkedNode:
4	def __init__(self, key: int = 0, val: int = 0) -> None:
5	self.key = key # Stored so eviction can delete the map entry
6	self.val = val
7	self.prev: Optional["DLinkedNode"] = None
8	self.next: Optional["DLinkedNode"] = None
9
10	class LRUCache:
11	"""LRU Cache: hash map for O(1) lookup + doubly-linked list for O(1) recency order.
12	Time: O(1) get and put \| Space: O(capacity)
13	"""
14	def __init__(self, capacity: int) -> None:
15	self.cap = capacity
16	self.cache: dict[int, DLinkedNode] = {}
17	self.head = DLinkedNode() # Sentinel: most recent side
18	self.tail = DLinkedNode() # Sentinel: least recent side
19	self.head.next = self.tail
20	self.tail.prev = self.head
21
22	def _remove(self, node: DLinkedNode) -> None:
23	node.prev.next = node.next # Unlink: sentinels mean no null checks
24	node.next.prev = node.prev
25
26	def _add_to_head(self, node: DLinkedNode) -> None:
27	node.prev = self.head
28	node.next = self.head.next
29	self.head.next.prev = node
30	self.head.next = node
31
32	def get(self, key: int) -> int:
33	# 1. Return A Miss, Or Promote The Found Node To Most Recently Used:
34	# A successful read counts as a use just like a write, so the node must move to the front
35	# before its value is returned; otherwise the node next to tail could stop being the least-recently-used one.
36	if key not in self.cache:
37	return -1
38	node = self.cache[key]
39	self._remove(node) # A read counts as a use:
40	self._add_to_head(node) # move to the most recent position
41	return node.val
42
43	def put(self, key: int, value: int) -> None:
44	# 1. Update In Place And Promote, Or Insert A New Node (Evicting If Full):
45	# An existing key keeps its map entry and only moves to the front; a brand-new key may first
46	# evict the node next to tail, which is always the least recently used because every use moves its node to the front.
47	if key in self.cache:
48	node = self.cache[key]
49	node.val = value # Update in place, then mark as most recent
50	self._remove(node)
51	self._add_to_head(node)
52	else:
53	if len(self.cache) >= self.cap:
54	lru = self.tail.prev # Least recently used sits next to the tail
55	self._remove(lru)
56	del self.cache[lru.key]
57	new_node = DLinkedNode(key, value)
58	self.cache[key] = new_node
59	self._add_to_head(new_node)

Gotchas1 of 4

The trap
Gotcha 1: Updating node.val without moving the node to the front
Mistake
```
node.val = value
```
Fix
```
node.val = value
self._remove(node)
self._add_to_head(node)
```
What happens: put on a cached key is a use, like get. Without the move, the node keeps its old place near tail. With capacity 2, put(1, 1), put(2, 2), put(1, 9) and put(3, 3) then evict key 1. Key 2 was used less recently, so key 2 must be evicted.
Example: capacity = 2: put(1, 1), put(2, 2), put(1, 9), put(3, 3), then get(1) and get(2)
Mistake: returns (-1, 2)Fix: returns (9, -1)
Gotcha 2: Evicting the node without del self.cache[lru.key]
Mistake
```
self._remove(lru)
```
Fix
```
self._remove(lru)
del self.cache[lru.key]
```
What happens: Eviction must remove the key from the map as well as the node from the list. Each node stores its key for exactly this line. Without it, the map keeps the evicted key. A later get finds it and returns a value that was evicted.
Example: capacity = 1: put(1, 1), put(2, 2), then get(1)
Mistake: returns 1Fix: returns -1
Gotcha 3: Calling _add_to_head before _remove in get
Mistake
```
self._add_to_head(node)
self._remove(node)
return node.val
```
Fix
```
self._remove(node)
self._add_to_head(node)
return node.val
```
What happens: _add_to_head(node) links the node after head, but its old neighbours still point to it. _remove(node) then uses the new node.prev and node.next, so it unlinks the node only from the front. The list is now broken. In this example, put(3, 5) evicts key 2, which get(2) has just read, and keeps key 1.
Example: capacity = 2: put(2, 2), put(1, 9), get(2), put(3, 5), then get(1)
Mistake: returns 9Fix: returns -1
Gotcha 4: Evicting when put updates a key that is already cached
Mistake
```
def put(self, key: int, value: int) -> None:
    if len(self.cache) >= self.cap:  # runs for every put
        lru = self.tail.prev
```
Fix
```
else:
    if len(self.cache) >= self.cap:
        lru = self.tail.prev
```
What happens: Updating a cached key adds no entry, so the cache does not grow. Eviction belongs only in the branch for a new key. With capacity 2, put(1, 1), put(2, 2) and put(2, 5) must keep both keys. Evicting on the update removes key 1.
Example: capacity = 2: put(1, 1), put(2, 2), put(2, 5), then get(1)
Mistake: returns -1Fix: returns 1

Canonical LeetCode:LRU Cache (LC 146)LFU Cache (LC 460)All O`one Data Structure (LC 432)First Unique Number (LC 1429)Design Authentication Manager (LC 1797)

Open the LRU Cache card

4Insert Delete GetRandom

values list + index map ➔ move the last value into the gap ➔ O(1) delete and uniform pick

Array + Index Map (Swap-with-Last Delete)

Spot it when: A set (or a multiset) must support insert, remove and a random pick where every stored value is equally likely (or weighted by its copies), each in O(1) on average.

Mode 4 · Insert Delete GetRandom

Python

1	import random
2
3
4	class RandomizedSet:
5	"""Insert Delete GetRandom O(1): a gap-free list for the random pick, a map for each value's slot.
6	Time: O(1) average per call \| Space: O(N)
7	"""
8
9	def __init__(self) -> None:
10	self.values: list[int] = [] # Every value once, no gaps: random.choice is uniform
11	self.index: dict[int, int] = {} # value -> its slot in self.values
12
13	def insert(self, val: int) -> bool:
14	# 1. Reject A Duplicate, Else Append At The Next Free Slot:
15	# The list is always gap-free, so its current length is exactly the slot the new value will occupy.
16	if val in self.index:
17	return False
18	self.index[val] = len(self.values) # The next free slot is the end
19	self.values.append(val)
20	return True
21
22	def remove(self, val: int) -> bool:
23	# 1. Fill val's Slot With The Last Value, Then Drop The Last Slot:
24	# A set has no order, so moving the last value into the freed slot keeps the list gap-free
25	# without shifting anything; the moved value's own map entry must be fixed before val's entry is deleted.
26	if val not in self.index:
27	return False
28	i = self.index[val]
29	last = self.values[-1]
30	self.values[i] = last # Fill the hole with the last value
31	self.index[last] = i # Update the moved value's slot first...
32	del self.index[val] # ...then delete: right even when last == val
33	self.values.pop() # The last slot is now a copy: drop it in O(1)
34	return True
35
36	def getRandom(self) -> int:
37	return random.choice(self.values) # One slot per value: each has a 1-in-n chance

Gotchas1 of 3

The trap
Gotcha 1: Deleting self.index[val] before writing self.index[last]
Mistake
```
del self.index[val]
self.index[last] = i
```
Fix
```
self.index[last] = i
del self.index[val]
```
What happens: When val is the last value, last == val. Deleting first removes val, then self.index[last] = i writes it back. pop() removes the slot, but the map still says that val is present. A later insert(val) then returns False.
Example: insert(1), remove(1), then insert(1)
Mistake: returns FalseFix: returns True
Gotcha 2: Popping the last slot before filling the hole
Mistake
```
self.values.pop()
self.values[i] = last
self.index[last] = i
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: When val is the only value, pop() leaves an empty list. self.values[i] = last then writes to slot 0, which no longer exists. So the call raises IndexError. Filling the hole first and popping last works for every i.
Example: insert(1), then remove(1)
Mistake: raises IndexErrorFix: returns True
Gotcha 3: Removing with self.values.pop(i) instead of moving the last value
Mistake
```
self.values.pop(i)
del self.index[val]
```
Fix
```
self.values[i] = last
self.index[last] = i
del self.index[val]
self.values.pop()
```
What happens: pop(i) shifts every value after slot i one slot to the left. That costs O(N) time. The shifted values keep their old slots in self.index, so the map points one slot too far. A later remove of a shifted value reads the wrong slot. self.values.remove(val) has the same two problems.
Example: insert(1), insert(2), insert(3), remove(1), then remove(3)
Mistake: raises IndexErrorFix: returns True

Canonical LeetCode:Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Open the Insert Delete GetRandom card

5Fenwick Tree

array ➔ isolate lowbit = x & (-x) ➔ O(log N) prefix query & update

Fenwick Tree (Binary Indexed Tree)

Spot it when: The array changes (single-element updates) and you still need prefix or range sums fast, or you count how many earlier values are smaller as you go.

Mode 5 · Fenwick Tree

Python

1	class FenwickTree:
2	"""Binary Indexed Tree (Fenwick Tree) for 1-indexed range sums.
3	Time: O(log N) update & query \| Space: O(N)
4	"""
5	def __init__(self, n: int):
6	self.n = n
7	self.tree = [0] * (n + 1)
8
9	def update(self, i: int, delta: int) -> None:
10	"""Add delta to index i (1-indexed)."""
11	# 1. Walk Up, Fixing Every Block That Covers i:
12	# Adding the lowest set bit jumps from i to the next larger block that still contains it,
13	# so this visits exactly the blocks whose stored sum needs delta added.
14	while i <= self.n:
15	self.tree[i] += delta
16	i += i & (-i) # Step up to parent covering range
17
18	def query(self, i: int) -> int:
19	"""Sum elements from 1 to i (1-indexed)."""
20	total = 0
21
22	# 1. Walk Down, Adding Disjoint Blocks:
23	# Removing the lowest set bit jumps to just before the block tree[i] covers, so each block
24	# added is disjoint from the ones before it, and together they cover exactly 1..i once.
25	while i > 0:
26	total += self.tree[i]
27	i -= i & (-i) # Step down to next disjoint prefix
28	return total
29
30	def range_query(self, left: int, right: int) -> int:
31	"""Sum in range [left, right] inclusive."""
32	return self.query(right) - self.query(left - 1)
33
34
35	class NumArray:
36	"""Range Sum Query - Mutable: keep the values, send each change to the Fenwick tree."""
37	def __init__(self, nums: list[int]):
38	self.nums = list(nums)
39	self.fenwick = FenwickTree(len(nums))
40
41	# 1. Seed The Tree With Every Starting Value:
42	# Each 0-based position lives one slot higher in the 1-indexed tree, so index + 1 is its i.
43	for index, val in enumerate(nums):
44	self.fenwick.update(index + 1, val) # Position index lives at i = index + 1
45
46	def update(self, index: int, val: int) -> None:
47	self.fenwick.update(index + 1, val - self.nums[index]) # Add the change, not the new value
48	self.nums[index] = val
49
50	def sumRange(self, left: int, right: int) -> int:
51	return self.fenwick.range_query(left + 1, right + 1)

Gotchas1 of 5

The trap
Gotcha 1: Calling update(index, val) with a 0-based index
Mistake
```
self.fenwick.update(index, val)
```
Fix
```
self.fenwick.update(index + 1, val)
```
What happens: The tree is 1-indexed. For i = 0, i & (-i) is 0, so i += i & (-i) leaves i at 0. The loop while i <= self.n then never ends. Shift every position up by one, so nums[index] lives at i = index + 1.
Example: nums = [1, 3, 5], then sumRange(0, 2)
Mistake: the loop never endsFix: returns 9
Gotcha 2: Shifting right but not left in sumRange
Mistake
```
return self.fenwick.range_query(left, right + 1)
```
Fix
```
return self.fenwick.range_query(left + 1, right + 1)
```
What happens: range_query(left, right) returns query(right) - query(left - 1). With left not shifted, it subtracts the sum up to position left - 1. Position left - 1 holds nums[left - 2], so the result also counts nums[left - 1].
Example: nums = [1, 3, 5], then sumRange(1, 2)
Mistake: returns 9Fix: returns 8
Gotcha 3: Adding the new value instead of the change
Mistake
```
self.fenwick.update(index + 1, val)
```
Fix
```
self.fenwick.update(index + 1, val - self.nums[index])
```
What happens: FenwickTree.update adds delta to a position. It can't set a value. To change nums[index] to val, add val - self.nums[index]. The blueprint keeps the current values in self.nums for this subtraction.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 11Fix: returns 8
Gotcha 4: Using raw values as positions instead of ranks 1..m
What happens: In Count of Smaller Numbers After Self (LC 315), the values can be negative or 0. From a position of 0 or below, i += i & (-i) reaches 0 and stays there. So update never ends. Replace each value by its rank 1..m among the sorted distinct values first. Then scan nums from the right.
Gotcha 5: Building with n calls to update when O(n) is needed
Mistake
```
for index, val in enumerate(nums):
    self.fenwick.update(index + 1, val)
```
Fix
```
for i in range(1, n + 1):
    self.tree[i] += nums[i - 1]
    parent = i + (i & -i)
    if parent <= n:
        self.tree[parent] += self.tree[i]
```
What happens: Each update visits up to log n positions, so n calls cost O(n log n) time. The one-pass build adds each tree[i] into its parent i + (i & -i) once. It gives the same tree in O(n) time. The sums are the same, and only the time changes.

Open the Fenwick Tree card

6Ordered Set

sorted keys ➔ bisect position ➔ floor and ceiling neighbours

Ordered Set (Floor/Ceiling Lookups)

Spot it when: You insert keys in any order and, between inserts, need the closest stored key at or below a value (the floor) or above it (the ceiling), as in My Calendar I (LC 729).

Mode 6 · Ordered Set

Python

1	import bisect
2
3
4	class MyCalendar:
5	"""My Calendar I: keep booked events sorted by start; a new event can only clash with its two neighbours.
6	Time: O(log N) search + O(N) insert per book, N = bookings so far \| Space: O(N)
7	"""
8	def __init__(self) -> None:
9	self.starts: list[int] = [] # Start times of booked events, kept sorted
10	self.ends: list[int] = [] # ends[j] is the end of the event that starts at starts[j]
11
12	def book(self, startTime: int, endTime: int) -> bool:
13	i = bisect.bisect_right(self.starts, startTime) # Events before i start at or before startTime
14
15	# 1. Reject An Overlap With Either Neighbour, Else Insert Between Them:
16	# The floor and ceiling are the only stored events that could possibly overlap the new one,
17	# since every other event sits sorted further away; both half-open checks must stay strict.
18	if i > 0 and self.ends[i - 1] > startTime:
19	return False # Floor neighbour is still running at startTime
20	if i < len(self.starts) and self.starts[i] < endTime:
21	return False # Ceiling neighbour starts before endTime
22	self.starts.insert(i, startTime) # Insert in place: starts stays sorted
23	self.ends.insert(i, endTime)
24	return True

Gotchas1 of 5

The trap
Gotcha 1: Writing >= instead of > in the floor check
Mistake
```
if i > 0 and self.ends[i - 1] >= startTime:
```
Fix
```
if i > 0 and self.ends[i - 1] > startTime:
```
What happens: Events are half-open, so [10, 20) and [20, 30) share no moment. With >=, an event that ends at 20 blocks one that starts at 20. The ceiling check self.starts[i] < endTime must stay strict for the same reason.
Example: book(10, 20), then book(20, 30)
Mistake: returns FalseFix: returns True
Gotcha 2: Checking only the floor neighbour
Mistake
```
self.starts.insert(i, startTime)
```
Fix
```
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
```
What happens: The floor is the stored event that starts at or before startTime. It can't see an event that starts inside the new one. After book(10, 20), the new event [5, 11) has no floor. Its ceiling [10, 20) starts before 11, so only the ceiling check rejects it. Checking only the ceiling fails the other way. It misses an event that is still running at startTime.
Example: book(10, 20), then book(5, 11)
Mistake: returns TrueFix: returns False
Gotcha 3: Appending to self.ends instead of inserting at i
Mistake
```
self.ends.append(endTime)
```
Fix
```
self.ends.insert(i, endTime)
```
What happens: self.ends[j] must be the end of the event that starts at self.starts[j]. append puts the end in the last slot, while the start went to slot i. The two lists then pair the wrong starts and ends, and later checks read the wrong end.
Example: book(10, 20), book(0, 5), then book(5, 10)
Mistake: returns FalseFix: returns True

Gotcha 4: Inserting the event before both checks pass

Mistake

self.starts.insert(i, startTime)
self.ends.insert(i, endTime)
if i > 0 and self.ends[i - 1] > startTime:
    return False

Fix

if i > 0 and self.ends[i - 1] > startTime:
    return False
if i < len(self.starts) and self.starts[i] < endTime:
    return False
self.starts.insert(i, startTime)
self.ends.insert(i, endTime)

Example: book(10, 20), book(15, 25), then book(20, 30)

Mistake: returns FalseFix: returns True

Gotcha 5: Expecting list.insert to take O(log N) time
What happens: bisect_right finds i in O(log N) time, but list.insert shifts every later entry. So one book costs O(N) time. My Calendar I (LC 729) allows at most 1000 calls, so the list is fast enough there. For many more bookings, use a balanced tree with the same floor and ceiling logic. Examples are Java's TreeMap, C++'s std::map and Python's sortedcontainers.SortedList.

Canonical LeetCode:My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)Range Module (LC 715)

Open the Ordered Set card

7Merge Sort Counting

pairs i < j ➔ count across two sorted halves ➔ merge

Merge Sort Counting (Reverse Pairs, Count of Range Sum)

Mode 7 · Merge Sort Counting

Python

1	def reverse_pairs(nums: list[int]) -> int:
2	"""Reverse Pairs: count the pairs that cross the middle while both halves are sorted, then merge.
3	Time: O(N log N) \| Space: O(N)
4	"""
5	def sort_count(lo: int, hi: int) -> int:
6	# 1. Handle One Value, Then Count Each Half On Its Own:
7	# A range of one value holds no pair; otherwise the recursive calls count every pair
8	# that does not cross this range's middle, and hand back two sorted halves.
9	if hi - lo <= 1:
10	return 0
11	mid = (lo + hi) // 2
12	count = sort_count(lo, mid) + sort_count(mid, hi)
13
14	# 2. Count The Pairs That Cross The Middle, While Both Halves Are Still Sorted:
15	# nums[i] only grows as i moves through the sorted left half, so the right values
16	# that pair with it, nums[mid:j], can only grow too; j never has to move back.
17	j = mid
18	for i in range(lo, mid):
19	while j < hi and nums[i] > 2 * nums[j]:
20	j += 1
21	count += j - mid
22
23	# 3. Merge The Two Sorted Halves, Now That Counting Is Done:
24	# The merge moves by plain order, nums[a] <= nums[b], not by the pair's own test, so
25	# counting must happen first, in its own pass; merging afterwards hands the parent a
26	# sorted range.
27	merged: list[int] = []
28	a, b = lo, mid
29	while a < mid and b < hi:
30	if nums[a] <= nums[b]:
31	merged.append(nums[a])
32	a += 1
33	else:
34	merged.append(nums[b])
35	b += 1
36	merged.extend(nums[a:mid])
37	merged.extend(nums[b:hi])
38	nums[lo:hi] = merged
39	return count
40
41	return sort_count(0, len(nums))

Gotchas1 of 5

The trap
Gotcha 1: Counting pairs inside the merge loop
Mistake
```
else:
    if nums[a] > 2 * nums[b]:
        count += mid - a
    merged.append(nums[b])
    b += 1
```
Fix
```
j = mid
for i in range(lo, mid):
    while j < hi and nums[i] > 2 * nums[j]:
        j += 1
    count += j - mid
```
What happens: The merge moves a and b by the test nums[a] <= nums[b]. The pair test is a different one, nums[i] > 2 * nums[j]. So the merge can move past a right value before it is tested against the larger left values. The separate pass tests every left value with its own pointer j.
Example: nums = [3, 5, 2, 1]
Mistake: returns 2Fix: returns 3
Gotcha 2: Calling sort_count(lo, mid + 1) with an exclusive hi
Mistake
```
count = sort_count(lo, mid + 1) + sort_count(mid, hi)
```
Fix
```
count = sort_count(lo, mid) + sort_count(mid, hi)
```
What happens: hi is exclusive, so sort_count(lo, mid) already covers the left half. Take a range of two values, lo and lo + 2. Then mid is lo + 1, and sort_count(lo, mid + 1) calls the same range again. The calls repeat until Python raises a RecursionError.
Example: nums = [2, 1]
Mistake: raises RecursionErrorFix: returns 0
Gotcha 3: Resetting j = mid for every i
Mistake
```
for i in range(lo, mid):
    j = mid
```
Fix
```
j = mid
for i in range(lo, mid):
```
What happens: The answer stays correct. But j then walks the right half again for every left value. Each merge step becomes quadratic, and the whole sort is O(N^2). The left half is sorted, so the right values that pair with nums[i] also pair with every later nums[i]. Keep j where it stopped.
Gotcha 4: Testing nums[i] >= 2 * nums[j]
Mistake
```
while j < hi and nums[i] >= 2 * nums[j]:
```
Fix
```
while j < hi and nums[i] > 2 * nums[j]:
```
What happens: Reverse Pairs (LC 493) needs nums[i] to be strictly greater than 2 * nums[j]. With >=, a pair where nums[i] equals 2 * nums[j] is counted too.
Example: nums = [2, 1]
Mistake: returns 1Fix: returns 0
Gotcha 5: Halving with nums[i] // 2 > nums[j]
Mistake
```
while j < hi and nums[i] // 2 > nums[j]:
```
Fix
```
while j < hi and nums[i] > 2 * nums[j]:
```
What happens: // rounds down. For an odd nums[i], such as 7, 7 // 2 is 3, and the pair 7 and 3 is missed. 7 > 2 * 3 is True, so it is a pair. Python never overflows on 2 * nums[j]. In Java or C++, compute it in 64 bits instead of halving.
Example: nums = [7, 3]
Mistake: returns 0Fix: returns 1

Open the Merge Sort Counting card

8Segment Tree

array ➔ binary tree of range sums ➔ O(log N) point update & range sum

Segment Tree (Range Sums With Point Updates)

Mode 8 · Segment Tree

Python

1	class SegmentTree:
2	"""Sum Segment Tree with Point Updates.
3	Node i covers [left, right]; its children are 2i+1 (left half) and 2i+2 (right half).
4	Time: O(N) build, O(log N) query & update \| Space: O(N)
5	"""
6	def __init__(self, nums: list[int]) -> None:
7	self.n = len(nums)
8	self.tree = [0] * (4 * self.n) # tree[node] is the sum of the slots node covers; 4n is always enough room
9	self._build(nums, 0, 0, self.n - 1)
10
11	def _build(self, nums: list[int], node: int, left: int, right: int) -> None:
12	# 1. Fill A Leaf With Its One Element, Else Build Both Halves First:
13	# A node's sum is the sum of its two halves, so both children must be built before this node can combine them.
14	if left == right:
15	self.tree[node] = nums[left] # Leaf: one array element
16	return
17	mid = (left + right) // 2
18	self._build(nums, 2 * node + 1, left, mid)
19	self._build(nums, 2 * node + 2, mid + 1, right)
20	self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Combine the two halves
21
22	def update(self, index: int, val: int, node: int = 0, left: int = 0, right: int = -1) -> None:
23	# 1. Default The Range, Then Stop At The Leaf For index:
24	# The first call omits left/right, so they default here; once left == right only one
25	# slot is left in the range, and that slot is index, so the leaf's own value is set.
26	if right == -1:
27	right = self.n - 1 # Default: start at the whole range
28	if left == right:
29	self.tree[node] = val # Reached the leaf for index
30	return
31
32	# 2. Recurse Into The Half That Contains index, Then Recompute On The Way Up:
33	# index lies in exactly one half, so only one child is visited; recomputing this node's
34	# sum from both children afterward keeps every ancestor's stored sum in sync with the new leaf.
35	mid = (left + right) // 2
36	if index <= mid:
37	self.update(index, val, 2 * node + 1, left, mid) # Go left
38	else:
39	self.update(index, val, 2 * node + 2, mid + 1, right) # Go right
40	self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2] # Recompute on the way up
41
42	def query(self, ql: int, qr: int, node: int = 0, left: int = 0, right: int = -1) -> int:
43	# 1. Default The Range, Then Resolve Full Overlap Or No Overlap:
44	# A node fully inside [ql, qr] can answer from its own stored sum; a node fully outside
45	# contributes 0, since it holds none of the requested slots.
46	if right == -1:
47	right = self.n - 1
48	if ql <= left and right <= qr:
49	return self.tree[node] # Fully inside the query: use the stored sum
50	if right < ql or left > qr:
51	return 0 # Fully outside: contributes nothing
52
53	# 2. Split On Partial Overlap And Add Both Halves:
54	# Neither child's range is fully inside or outside, so both are queried and their sums are added.
55	mid = (left + right) // 2 # Partial overlap: split into both halves
56	return (self.query(ql, qr, 2 * node + 1, left, mid) +
57	self.query(ql, qr, 2 * node + 2, mid + 1, right))
58
59
60	class NumArray:
61	"""Range Sum Query - Mutable: every call goes straight to the segment tree."""
62	def __init__(self, nums: list[int]):
63	self.seg = SegmentTree(nums)
64
65	def update(self, index: int, val: int) -> None:
66	self.seg.update(index, val) # The leaf is overwritten with val, then its ancestors recomputed
67
68	def sumRange(self, left: int, right: int) -> int:
69	return self.seg.query(left, right)

Gotchas1 of 5

The trap
Gotcha 1: Changing the leaf but not recomputing its ancestors
Mistake
```
else:
    self.update(index, val, 2 * node + 2, mid + 1, right)
```
Fix
```
else:
    self.update(index, val, 2 * node + 2, mid + 1, right)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
```
What happens: update changes the leaf for index, then returns up the recursion. Each node on the way holds the sum of its range. Without the line self.tree[node] = ..., those nodes keep their old sum. A later query that fully covers such a node returns its stored self.tree[node] and misses the new value. For nums = [1, 3, 5], the root keeps 9 after update(1, 2), although the sum is now 8.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 9Fix: returns 8
Gotcha 2: Using a stored sum when the node only overlaps the query
Mistake
```
if left <= qr and ql <= right:
```
Fix
```
if ql <= left and right <= qr:
```
What happens: self.tree[node] is the sum of every slot the node covers. A node that only overlaps [ql, qr] also covers slots outside it. With the overlap test, query returns that whole sum and never asks the two children. The extra slots are counted in the answer. The correct test returns the stored sum only when the node lies inside [ql, qr].
Example: nums = [1, 3, 5], then sumRange(0, 1)
Mistake: returns 9Fix: returns 4
Gotcha 3: Adding val to the leaf instead of setting it
Mistake
```
self.tree[node] += val
```
Fix
```
self.tree[node] = val
```
What happens: LeetCode's update(index, val) replaces nums[index] with val. This tree stores the slot values themselves in its leaves, so the leaf must be set to val. With +=, the leaf holds the old value plus val. A Fenwick tree is different: it only adds, so it receives the change val - old.
Example: nums = [1, 3, 5], update(1, 2), then sumRange(0, 2)
Mistake: returns 11Fix: returns 8
Gotcha 4: Allocating 2 * n nodes instead of 4 * n
Mistake
```
self.tree = [0] * (2 * self.n)
```
Fix
```
self.tree = [0] * (4 * self.n)
```
What happens: With children at 2 * node + 1 and 2 * node + 2, the tree has gaps when n is not a power of two. Some nodes then get an index of 2 * n or more. With only 2 * n slots, _build raises IndexError when it reaches such a node. 4 * n slots are always enough.
Example: nums = [1, 2, 3, 4, 5, 6], then sumRange(0, 5)
Mistake: raises IndexErrorFix: returns 21
Gotcha 5: Updating a whole range one element at a time
What happens: This tree changes one position per update, in O(log N) time. Changing every value in a range this way costs O(log N) for each element of the range. For many range updates, use lazy propagation. It stores a pending change at a node and passes it to the children only when a query or update goes below that node.

Canonical LeetCode:Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)Count of Range Sum (LC 327)Reverse Pairs (LC 493)

Open the Segment Tree card

Built on the mental models above

Max Segment TreeMax Segment Tree (Range Maximum Query)
Each node keeps the maximum instead of the sum, so an update writes max(...) and a query takes max over the covered nodes.

The Advanced Data Structures Decision Rule

When facing an unseen system design or data structure problem, ask in this order:

Step 1.Does the problem involve prefix matching, autocomplete, or multi-word grid search?

➔ Trie

Implement Trie (Prefix Tree) (LC 208)Design Add and Search Words Data Structure (LC 211)

Build Trie and descend character by character in O(L) time.

Step 2.Does the problem group elements into dynamic connected components or detect undirected cycles?

➔ Union-Find

Redundant Connection (LC 684)Number of Provinces (LC 547)

Maintain parent and rank arrays in O(alpha(N)).

Step 3.Does the problem require frequent point updates and prefix sum range queries?

➔ Fenwick Tree

Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)

Implement 1-indexed BIT using lowbit = i & -i.

Step 4.Do range queries mix with updates, where each tree node must store a range sum, or something a Fenwick tree can't do easily (range max or min, a change to a whole range)?

➔ Segment Tree

Range Sum Query - Mutable (LC 307)Count of Smaller Numbers After Self (LC 315)

Each node stores its segment's aggregate (here the sum of its slots); updates and queries touch O(log N) nodes, with lazy tags for range updates.

Step 5.Does each step need the largest value in a window of slots, and then a change at one slot?

➔ Max Segment Tree

Longest Increasing Subsequence II (LC 2407)Fruits Into Baskets III (LC 3479)

Store the maximum in every node of a segment tree; an update recomputes the maximum of each ancestor, and a query takes the maximum over the covered nodes.

Step 6.While inserting keys, do you need the closest key at or above (or at or below) a value?

➔ Ordered Set

My Calendar I (LC 729)Data Stream as Disjoint Intervals (LC 352)

Keep the keys sorted (SortedList) and bisect for the floor and the ceiling in O(log N).

Step 7.Does the problem require O(1) key-value lookup with recency eviction?

➔ LRU Cache

LRU Cache (LC 146)LFU Cache (LC 460)

Pair a Hash Map with a Doubly-Linked List with sentinel head/tail.

Step 8.Must a set support insert, remove and a uniform random pick, each in O(1) on average?

➔ Insert Delete GetRandom

Insert Delete GetRandom O(1) (LC 380)Insert Delete GetRandom O(1) - Duplicates allowed (LC 381)

Store values in a list plus a value-to-index map; remove by moving the last value into the gap and popping.

Step 9.Must you count the pairs of positions (i < j) whose values are in a given order, or differ by more than a limit, without checking every pair?

➔ Merge Sort Counting

Reverse Pairs (LC 493)Count of Smaller Numbers After Self (LC 315)

Sort with merge sort, and count the pairs between the two sorted halves just before each merge, in O(N log N).

Pattern Architecture & Invariant Design Masterclass

The one subtlety, and it is the whole interview question: a path existing does not mean a word was stored. After inserting "apple", the path for "app" exists — it is a stretch of "apple"'s path. Every node therefore needs a boolean flag marking "a word ends exactly here." Searching checks the flag; prefix-matching does not. Getting that distinction wrong is the classic Trie bug.

The one subtlety: naively, the parent chains grow into long lists and every query walks them, degrading to O(n). Two small fixes — path compression (re-point every node you pass directly at the root) and union by size (always hang the smaller tree under the larger) — make every operation effectively constant time.

🔬 Variable Anatomy: The 7 Variables Every Trie & Union-Find Uses

To connect abstract specialized tree structures with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

# =============================================================================
# 1. TRIE MASTER STRUCTURE
# =============================================================================
class TrieNode:
    def __init__(self):
        self.children = {}       # 🔤 Outgoing Character Edges: char -> TrieNode
        self.is_end = False      # 🚩 Terminal Word Flag: True ONLY on final char of stored word
 
class TrieMasterTemplate:
    def __init__(self):
        self.root = TrieNode()   # ⚓ Empty Prefix Root Anchor
 
    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_end = True       # ⚠️ Set True strictly on the terminal node
 
    def search(self, word: str) -> bool:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return curr.is_end       # ⚠️ Requires is_end == True
 
    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for ch in prefix:
            if ch not in curr.children:
                return False
            curr = curr.children[ch]
        return True              # ⚠️ Prefix existence is sufficient
 
 
# =============================================================================
# 2. DISJOINT SET UNION (UNION-FIND) MASTER STRUCTURE
# =============================================================================
class UnionFindMasterTemplate:
    def __init__(self, size: int):
        self.parent = list(range(size))  # 🔗 Representative Parent Pointers
        self.rank = [1] * size           # 🌲 Component Tree Size / Rank
        self.num_components = size       # 🔢 Total Disjoint Components
 
    def find(self, x: int) -> int:
        # Path Compression: flatten traversal path directly to root
        root = x
        while root != self.parent[root]:
            root = self.parent[root]
        
        curr = x
        while curr != root:
            nxt = self.parent[curr]
            self.parent[curr] = root     # ⚡ Point directly to canonical root
            curr = nxt
        return root
 
    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # 🚫 Already connected (Cycle detected!)
 
        # Union by Rank / Size: hang smaller tree under larger root
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.rank[ra] += self.rank[rb]
        self.num_components -= 1
        return True

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`root`	`TrieNode` anchor	"Where does prefix exploration begin?"	❌ Storing characters on root confuses empty prefix `""` with 1-character words.
`children`	`dict[str, TrieNode]`	"Does an edge exist for the next character in this prefix?"	❌ Using fixed 26-element arrays crashes on uppercase or non-ASCII characters without index mapping.
`is_end`	Boolean flag	"Did a stored word terminate at this node, or is it merely a prefix?"	❌ If `search` returns `True` without checking `is_end`, `search("app")` returns `True` after only inserting `"apple"`.
`parent`	`list[int]`	"Who is the immediate ancestor / canonical representative of node $x$ ?"	❌ Comparing `parent[a] == parent[b]` instead of `find(a) == find(b)` fails on deep unflattened trees.
`rank` / `size`	`list[int]`	"Which tree has larger depth/size to serve as root during union?"	❌ Without union-by-rank, parent chains degenerate into $O(N)$ linked lists.
`num_components`	Integer count	"How many independent connected clusters remain after dynamic edges?"	❌ Without decrementing on valid unions, calculating active components requires an $O(N)$ scan.
`lowbit`	`i & (-i)`	"What is the step size for Fenwick tree navigation?"	❌ In Binary Indexed Trees, calculating lowbit without two's complement requires loop searches.

🧠 The Universal Contracts of Advanced Containers:

Trie Invariant: Word length $L$ , not dataset size $N$ , dictates latency. Insertion and search are strictly $O(L)$ .

Union-Find Invariant: With both Path Compression and Union-by-Rank, the amortized cost per operation is $O(\alpha(N))$ (inverse Ackermann function $\le 4$ for all physical universe inputs).

🌟 The 3 Dimensions of Advanced Data Structures & Structural Invariants

Every Advanced Data Structure is governed by 3 Key Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                 THE 3 DIMENSIONS OF ADVANCED DATA STRUCTURES                │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. TARGET DOMAIN  │ Character paths (Trie) vs         │ "Are we indexing    │
│    SPECIALIZATION │ Equivalence partitions (DSU)      │ prefixes or sets?"  │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. LATENCY BOUND  │ O(L) per word (Trie) vs           │ "How does runtime   │
│    INVARIANT      │ O(alpha(N)) amortized (DSU)       │ scale with input?"  │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. STRUCTURAL     │ Node flag separation (`is_end`) vs│ "How do we compress │
│    COMPRESSION    │ In-place pointer flattening       │ path traversal?"    │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: Prefix Searching & Autocomplete (Trie)

When querying millions of words for common prefixes, hashing every prefix consumes $O(N \cdot L^2)$ memory.
The Rule: Build a 26-ary character tree. Descend one character edge per step. Prefix lookup stops when characters survive; word search requires curr.is_end == True.
The Result: $O(L)$ exact and prefix searches independent of dictionary volume.

🔵 Scenario B: Dynamic Connectivity & Undirected Cycle Detection (Union-Find)

When edges arrive incrementally in a graph, running DFS/BFS to check connectivity after each edge takes $O(E \cdot (V + E))$ .
The Rule: Initialize parent[i] = i. For edge $(u, v)$ , compute ra, rb = find(u), find(v). If ra == rb, a cycle exists! Otherwise merge with union(u, v).
The Result: Near-instant $O(\alpha(N))$ connectivity verification per edge.

💡 The Ultimate Takeaway Decision Rule:
When analyzing an unseen data structure problem, ask: "Is this a string prefix problem, or an incremental set-merging problem?"

If Prefix matching / Autocomplete / Word Boggle ➔ Build a Trie ( $O(L)$ query).

If Dynamic connected components / Redundant connections ➔ Build Union-Find with Path Compression ( $O(\alpha(N))$ ).

If Frequent prefix sum point updates ➔ Build a Fenwick Tree / BIT ( $O(\log N)$ ).

🎯 The 5 Essential Advanced Data Structures Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                               THE 5 CORE ADVANCED DATA STRUCTURE ARCHETYPES                                      │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Container Mechanism  │ Invariant / Structural Rule   │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. Trie Prefix Tree    │ 26-ary character tree│ `is_end` required for search; │ Implement Trie (LC 208), Add &   │
│    (LC 208 / LC 211)   │ with `is_end` flag   │ prefix only checks traversal  │ Search Words (LC 211) — O(L)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Trie + 2D Matrix    │ Trie coupled with    │ Prune grid branches when Trie │ Word Search II (LC 212) —        │
│    (LC 212)            │ in-place DFS marking │ node child is missing         │ O(R * C * 4^L) with fast pruning │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. DSU Cycle Detection │ Disjoint Set Union   │ Edge redundant iff roots match│ Redundant Connection (LC 684) —  │
│    (LC 684 / LC 547)   │ with Path Compression│ `find(u) == find(v)`          │ O(E * alpha(V))                  │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Equivalence Sets    │ DSU on mapped indices│ Connect distinct attributes to│ Accounts Merge (LC 721), Min     │
│    (LC 721 / LC 1584)  │ (email -> account id)│ single representative owner   │ Cost Connect Points (LC 1584)    │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 5. Fenwick Tree / BIT  │ 1-indexed array with │ `lowbit = i & -i` steps parent│ Range Sum Query Mutable (LC 307) │
│    (LC 307 / LC 315)   │ lowbit index jumps   │ prefix sums and point updates │ — O(log N) update and query      │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

🌲 1. Trie: Word Insertion and Verification (LC 208)

Mental Model: A Trie routes character sequences down shared trunk prefixes.
Code Blueprint:

Code / Blueprint

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def _walk(self, s: str):
        curr = self.root
        for ch in s:
            if ch not in curr.children:
                return None
            curr = curr.children[ch]
        return curr
 
    def insert(self, word: str) -> None:
        curr = self.root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_end = True
 
    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end
 
    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

🔍 2. Trie + 2D Matrix Search (LC 212 — Word Search II)

Mental Model: Loading words into a Trie allows exploring a 2D board once while searching for thousands of dictionary words simultaneously.
Pruning Invariant: If the current grid path character does not exist in the active Trie node's children, backtrack immediately without exploring 4-way neighbors.

🔗 3. Union-Find: Cycle Detection in Redundant Connections (LC 684)

Mental Model: Two vertices $u$ and $v$ are already connected if they share the same representative. An extra edge between them creates an undirected cycle.
Code Blueprint:

Code / Blueprint

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = list(range(n + 1))
    rank = [1] * (n + 1)
 
    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]
 
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]  # Cycle detected!
        # Union-by-rank: attach shallower tree under deeper tree
        if rank[ru] < rank[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        if rank[ru] == rank[rv]:
            rank[ru] += 1
    return []

📧 4. Equivalence Grouping (LC 721 — Accounts Merge)

Mental Model: Map every unique email to an integer identifier, union emails belonging to the same user account, and group all emails sharing the same root representative.

📈 5. Binary Indexed Tree / Fenwick Tree (LC 307)

Mental Model: Uses the binary representation of integers to store cumulative frequency intervals, enabling point updates and prefix sums in $O(\log N)$ time.

🌳 Evaluating Trie and DSU State & Space Invariants

Designing advanced custom containers requires understanding memory and pointer structures:

1. Trie Node Space vs Dictionary Allocations

Python dictionaries (children = {}) dynamically allocate space only for edges that exist, which is much more memory efficient than pre-allocating size-26 lists on sparse alphabets.
To prevent memory leaks in large grid searches, prune leaf nodes from the Trie when their words are found.

2. Union-Find 1-Indexing and Iterative Traversal

Many graph problems use 1-indexed vertex IDs. Always allocate parent = list(range(n + 1)) to avoid index out-of-range errors.
Prefer iterative path compression or single-pass path splitting over deep recursive find() calls on long degenerate chains.

💡 Staff SWE Architectural Invariant:
Choose Trie when the query space is bounded by character prefix lengths ( $O(L)$ ), and choose Disjoint Set Union when the problem involves dynamic equivalence clustering or cycle detection in undirected graphs ( $O(\alpha(N))$ ).

Understanding Invariants: Prefix Tree Termination & Disjoint Set Path Compression

A Trie node's is_end flag, not its path existence, determines if a word was stored. In Union-Find, two elements are connected if and only if find(a) == find(b).

Trie Terminal Word vs Prefix Invariant

Condition: In search(word), after consuming all characters, check curr.is_end

Action: return curr.is_end for exact word search, return True for startsWith(prefix)

A prefix path exists for any substring of an inserted word, but is_end == True only for words explicitly added.

Disjoint Set Union Cycle Detection Invariant

Condition: If find(u) == find(v) when processing an undirected edge (u, v)

Action: return False (union fails) and flag edge as a redundant cycle

Adding an edge between two vertices that already share the same canonical representative creates a cycle.

Common Questions

"If I can walk the whole word without falling off the Trie, doesn't that mean the word must be stored? Why do we need a separate is_end flag at all?"

Because a path existing and a word being stored are two different facts, and a Trie's whole efficiency comes from sharing paths between words that were never themselves inserted.

Trace it concretely: insert only "apple" into an empty Trie. The path a → p → p → l → e now exists. But the path a → p → p — spelling "app" — also exists, purely as a byproduct of walking through "apple"'s own path. If search("app") reused the "did I fall off the tree" test that startsWith correctly uses, it would answer True for "app", even though "app" was never inserted on its own.

The only fact that distinguishes "this node happens to lie on someone else's path" from "a word was deliberately stored ending exactly here" is a flag set at insert-time on that exact node, and checked at query-time on that exact node — nothing about the tree's shape encodes it, because sharing that shape between related words is the entire reason a Trie is cheap in the first place. That's why search is path exists AND is_end, while startsWith is path exists alone: startsWith("app") is legitimately asking "is there anything below this point," which mere path existence answers correctly, while search("app") asks the strictly stronger question "does a word end at this exact point," which only the flag can answer.

Coach discussion points

1.
"I inserted only 'apple'. Tell me what search('app') and startsWith('app') return, and explain why they differ when they walk to the same node." — The single highest-signal Trie question. A student who has genuinely built one answers instantly; one who has copied a template hesitates.
2.
"When is a hash set better than your Trie, and when is it useless?" — Tests whether the structure was chosen or reached for. The honest answer names the prefix query as the dividing line, and the construction cost as the price.
3.
"You wrote path compression. Suppose I delete it — what still works, and what stops working?" — Everything still works; it just gets slow, and only on large inputs. Distinguishing correctness bugs from performance bugs is a genuinely senior skill.
4.
"Your union returns False sometimes. What does the caller do with that, and what other problem does it solve?" — Cycle detection. Follow-up: "could you use this on a directed graph?" — No, and knowing why (DSU has no notion of edge direction) is the boundary-of-the-tool signal.
5.
"In Number of Islands II, why does a successful union() decrement the count, when in Redundant Connection a successful cycle check is union() returning False?" — Because the two problems ask opposite questions of the same primitive: Redundant Connection asks "did this edge create a redundant connection?" (answered by union() returning False), while Number of Islands II asks "did this operation productively merge two components?" (answered by union() returning True). A student who can articulate this duality has genuinely internalized DSU rather than memorized two separate templates.
6.
"Why can't you just reuse your LRU Cache's hash map + doubly-linked list for LFU, adding a freq field to each node?" — Because a single linked list can only maintain one total order. The moment two keys have different frequencies but you need both "which frequency is lowest" and "which key is oldest within that frequency," one list can't express two independent orderings at once. That's exactly why LFU needs a second hash map (freq -> bucket), not just an extra field.
7.
"Your min_freq pointer only ever increments, never decrements after a get. Walk me through exactly when it does change, and prove it's never stale." — It changes only when the bucket it currently points at becomes empty (advances by exactly 1, since frequencies increase by exactly 1 per access) or when a brand-new key is inserted (reset to 1, since a fresh key is trivially the new minimum). Proving it's never stale means showing no other code path can leave min_freq pointing at a bucket that no longer exists.
8.
**"All Oone needs both a max and a min in O(1). Why doesn't LFU Cache need the same trick for its min_freq-- couldn't you also track amax_freq?"** — LFU never needs the max frequency for anything; it only ever evicts from the min. Tracking a max_freq` you never read would be a real correctness liability (another pointer to keep consistent) for zero benefit -- a good check for whether a student is pattern-matching the bucket trick or actually reasoning about what each structure is asked to report.

Complexity analysis

Trie

Operation	Time	Why
`insert(word)`	`O(L)`	One dictionary lookup or insertion per character, each `O(1)`
`search(word)`	`O(L)`	Same walk, plus one flag read
`startsWith(prefix)`	`O(L)`	Same walk, no flag read

Union-Find

Operation	Time	Why
`find(x)`	`O(α(n))` amortised	With path compression and union by size
`union(a, b)`	`O(α(n))` amortised	Two finds plus one pointer write
Space	`O(n)`	Two integer arrays

What happens without the optimisations, stated exactly:

Neither optimisation: O(n) per operation — the structure degenerates into a linked list.
Path compression only: O(log n) amortised.
Union by size only: O(log n).
Both: O(α(n)). The near-constant bound needs both, and knowing that is the follow-up question.

LRU Cache

Operation	Time	Why
`get(key)`	`O(1)` average	Hash map pointer lookup + fixed-cost doubly-linked-list splice
`put(key, value)`	`O(1)` average	Hash map insertion + fixed-cost splice + at most one fixed-cost eviction
Space	`O(C)`	Hash map of size `C` + doubly linked list of `C + 2` nodes (`C` = capacity)

LFU Cache

Operation	Time	Why
`get(key)`	`O(1)` average	`key_node` lookup + `_bump_freq`'s fixed-cost bucket splice
`put(key, value)`	`O(1)` average	`key_node`/`freq_bucket` lookups + fixed-cost splice + at most one fixed-cost eviction
Space	`O(C)`	`key_node` map of size `C` + `freq_bucket` map whose bucket node counts sum to `C` (`C` = capacity)

All O`one Data Structure

Operation	Time	Why
`inc(key)` / `dec(key)`	`O(1)` average	`key_bucket` lookup + `_insert_after`'s fixed-cost reuse-or-splice + fixed-cost set add/remove
`getMaxKey()` / `getMinKey()`	`O(1)`	Direct peek at `tail.prev`/`head.next`'s key set, no traversal
Space	`O(K)`	`key_bucket` map of size `K` + bucket chain whose key sets sum to `K` (`K` = number of distinct keys currently tracked)

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Conflating path existence with word completion: search must verify node.is_end == True. Checking only that the character chain exists causes prefix-only matches (e.g. searching 'app' when only 'apple' was inserted) to incorrectly return True.
Omitting path compression (Union-Find). Every test with 10 elements passes; the one with 100,000 times out. The most common performance failure in this pattern.
Using a singly-linked list (LRU Cache). Removing a node needs its prev pointer; without one, removal degrades to O(N). This is the whole reason the structure is doubly linked.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES