Loading...
Master advanced data structures that unlock efficient solutions to complex problems: Union Find for dynamic connectivity, Tries for prefix-based string operations, LRU Cache for O(1) eviction, and Segment Trees for range queries. These structures appear frequently in system design and competitive programming.
Advanced data structures go beyond arrays, hash maps, and trees to solve specialized problems with optimal efficiency. Each structure in this chapter addresses a specific class of problems that would be significantly harder or slower to solve with basic data structures.
Union Find (Disjoint Set Union) maintains a partition of elements into non-overlapping sets, supporting near-constant-time merge and membership queries. It is the backbone of Kruskal's algorithm, network connectivity, and image segmentation.
Trie (Prefix Tree) stores strings character by character in a tree, enabling prefix searches, autocomplete, and dictionary lookups in time proportional to the word length rather than the dictionary size.
LRU Cache combines a hash map with a doubly linked list (or Python's OrderedDict) to provide O(1) get and put operations with automatic eviction of the least recently used entry when capacity is exceeded.
Segment Tree supports both range queries (sum, min, max over a subarray) and point updates in O(log n) time, making it indispensable for problems where the underlying array changes frequently.
This chapter covers:
Click any topic to jump in
Path compression + union by rank gives amortized $O(\alpha(n))$ per operation.
Static counting via DFS/DSU; dynamic connectivity via link-cut trees.
Each tackles a different aspect
$O(L)$ insert and search for prefix queries, independent of dictionary size.
DFS from prefix nodes and precomputed top-k lists for fast ranked suggestions.
Each tackles a different aspect
$O(1)$ get/put via hashmap + doubly linked list (or OrderedDict).
$O(\log n)$ range queries and point updates on any associative aggregate.
Union Find (also called Disjoint Set Union or DSU) is a data structure that tracks a collection of elements partitioned into non-overlapping sets. It supports two primary operations: find (determine which set an element belongs to) and union (merge two sets into one).
The naive implementation uses a parent array where each element points to its parent, with root elements pointing to themselves. Two critical optimizations make both operations run in nearly O(1) amortized time:
With both optimizations, the amortized time per operation is O(alpha(n)), where alpha is the inverse Ackermann function---effectively constant for all practical input sizes.
The find operation traverses parent pointers from an element up to the root of its set. Path compression flattens the tree during this traversal by making every visited node point directly to the root. This means subsequent find operations on any of those nodes complete in O(1). Without path compression, find could degrade to O(n) on a skewed tree. With it, the amortized cost drops to O(alpha(n)).
Path compression makes every node on the find path point directly to the root. Combined with union by rank, it gives amortized complexity per operation, where is the inverse Ackermann function. For all practical (even ), , so operations are effectively constant time.
Given parent = [0, 0, 1, 1, 3], what does the tree look like after calling find(4) with path compression?
When merging two sets, union by rank attaches the root of the shorter tree under the root of the taller tree. The rank of a node is an upper bound on its height. If both trees have the same rank, one becomes the child of the other and the new root's rank increases by 1. This keeps the overall tree height bounded by O(log n), ensuring that even without path compression, find operations are logarithmic.
Union by rank attaches the shorter tree under the taller tree's root, which keeps the tree depth at without path compression. With both heuristics, Tarjan proved the amortized bound per operation; omitting either one degrades to amortized, and omitting both gives worst case. Rank is an upper bound on height, not exact height, since path compression only shrinks trees.
Two sets have roots A (rank 2) and B (rank 1). How does union by rank merge them?