AlgoDaily

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?

Beyond Basic Containers

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 in O(log n)
  • poll() removes the smallest item by default in O(log n)
  • peek() reads the smallest item in O(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.

Range Query Problem

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 sums O(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.

Segment Tree

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:

  1. “The repeated operation is ___.”
  2. “A brute force approach would cost ___.”
  3. “This data structure reduces it to ___.”
  4. “The tradeoff is extra memory and implementation complexity.”

Next, we will shift from general containers to specialized techniques for text in String Algorithms.

Interview Selection Map

Open interactive view →