Advanced Data Structures
Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.
Beyond Basic Containers
Why advanced data structures?
Now that we've covered Arrays and Strings, Trees and Graphs, Dynamic Programming, Graph Algorithms, and Hashing, you can already solve many interview problems.
But MAANG-style interviews often add one extra constraint:
The data changes over time, and we still need fast answers.
A normal array can scan. A HashMap can find exact keys. A graph traversal can explore. Advanced data structures help when you need operations like:
- repeatedly getting the smallest/largest item
- checking whether two nodes are in the same connected group
- updating values while answering range queries quickly
Today is not about memorizing exotic names. It is about learning how to ask: what operation must be fast?

Heaps And Priority
When order matters dynamically
You already saw in Sorting and Searching that sorting creates useful order. But what if elements keep arriving and you only need the next best item?
That is where a heap shines.
In Java, the common interview tool is PriorityQueue:
-
offer(x)inserts inO(log n) -
poll()removes the smallest item by default inO(log n) -
peek()reads the smallest item inO(1)
Use a heap when the phrase sounds like:
- “top K”
- “k closest”
- “merge k sorted lists”
- “always process the smallest/largest next”
A heap does not fully sort everything. It keeps just enough structure to quickly expose the current priority item.
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {7, 2, 10, 4, 1};
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int x : nums) {
minHeap.offer(x);
}
System.out.println("Smallest: " + minHeap.peek());
System.out.print("Ascending order by repeated poll: ");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " ");
}
}
}
```
Choose The Tool
You are building a scheduler. Tasks arrive over time, and you repeatedly need to process the task with the smallest deadline.
Which data structure is the best fit?
Union Find
Fast connectivity checks
In Graph Algorithms, you practiced traversals and shortest paths. Sometimes we do not need a full traversal every time. We only need to know:
Are these two items in the same group?
Union-Find, also called Disjoint Set Union (DSU), supports two core operations:
-
find(x): return the representative/root of x's group -
union(a, b): merge the groups containing a and b
Common interview uses:
- detecting cycles in an undirected graph
- counting connected components
- grouping accounts/emails
- Kruskal's minimum spanning tree setup
With path compression and union by rank/size, operations are effectively constant for interview-sized input.
```java
public class Main {
static class UnionFind {
int[] parent;
int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) return false;
if (rank[rootA] < rank[rootB]) {
parent[rootA] = rootB;
} else if (rank[rootA] > rank[rootB]) {
parent[rootB] = rootA;
} else {
parent[rootB] = rootA;
rank[rootA]++;
}
return true;
}
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
System.out.println("0 connected to 2? " + (uf.find(0) == uf.find(2)));
System.out.println("0 connected to 4? " + (uf.find(0) == uf.find(4)));
}
}
```
Union Find Limits
True or false: Union-Find is a good replacement for Dijkstra's algorithm when we need shortest path distances in a weighted graph.
Range Query Problem
The next bottleneck: ranges
Suppose you have an array of scores:
index: 0 1 2 3 4
value: 2 4 5 7 1
You need to answer many questions like:
- “What is the sum from index 1 to 3?”
- “Update index 2 from 5 to 9.”
- “Now what is the sum from index 0 to 4?”
A prefix sum array gives fast range sums only if values do not change. Once updates happen, rebuilding prefix sums can become expensive.
This is where Fenwick Trees and Segment Trees enter. They store summary information so both updates and queries are fast.

Fenwick Tree
Compact prefix sums with updates
A Fenwick Tree, also called a Binary Indexed Tree, is excellent for:
- point updates: change one index
- prefix sum queries: sum from start to index
- range sum queries:
prefix(right) - prefix(left - 1)
Both update and query take O(log n).
The key idea: each internal position stores the sum of a small block. Java implementations often use 1-based indexing because the bit trick i += i & -i moves to the next responsible block.
```java
public class Main {
static class FenwickTree {
int[] tree;
FenwickTree(int n) {
tree = new int[n + 1]; // 1-based indexing
}
void add(int index, int delta) {
index++; // convert 0-based input to 1-based internal index
while (index < tree.length) {
tree[index] += delta;
index += index & -index;
}
}
int prefixSum(int index) {
index++; // convert to 1-based
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
int rangeSum(int left, int right) {
if (left == 0) return prefixSum(right);
return prefixSum(right) - prefixSum(left - 1);
}
}
public static void main(String[] args) {
int[] nums = {2, 4, 5, 7, 1};
FenwickTree bit = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; i++) {
bit.add(i, nums[i]);
}
System.out.println("Sum [1, 3]: " + bit.rangeSum(1, 3)); // 4 + 5 + 7
bit.add(2, 4); // nums[2] changes from 5 to 9
System.out.println("After update, sum [1, 3]: " + bit.rangeSum(1, 3));
}
}
```
Segment Tree
More flexible range summaries
A Segment Tree is another structure for dynamic range queries.
Compared with a Fenwick Tree:
Structure Best For Update Query Flexibility Fenwick Tree prefix/range sumsO(log n)
O(log n)
simpler, compact
Segment Tree
many range operations
O(log n)
O(log n)
more flexible
Segment Trees are useful when the summary is not just sum, for example:
- range minimum
- range maximum
- range greatest common divisor
- custom merge of interval data
Mental model: recursively split the array into intervals. Each tree node stores the answer for its interval. A query combines only the intervals needed.

Range Complexity
For a Fenwick Tree, both point update and prefix sum query usually take ____ time.
Interview Selection Map
How to recognize the pattern
When an interviewer gives you a problem, listen for the operation that repeats most often.
If the problem says... Think... “always take smallest/largest next” Heap /PriorityQueue
“connect groups” or “same component?”
Union-Find
“range sum with updates”
Fenwick Tree
“range min/max/custom query with updates”
Segment Tree
A strong interview answer is not just code. It sounds like:
- “The repeated operation is ___.”
- “A brute force approach would cost ___.”
- “This data structure reduces it to ___.”
- “The tradeoff is extra memory and implementation complexity.”
Next, we will shift from general containers to specialized techniques for text in String Algorithms.
