Advanced Topics
Advanced Data Structures and Techniques
These are the structures that appear when a problem needs repeated range queries, repeated prefix lookups, or repeated connectivity checks, and a linear scan per query is too slow. They come up in the harder end of interviews and constantly in competitive programming.
The material assumes the earlier topics are solid — segment trees make sense once binary trees do, and disjoint sets are much clearer after graph connectivity. Each lesson visualises the operation that gives the structure its advantage: the range decomposition in a segment tree, the path compression in a disjoint set, the shared prefixes in a trie.
Interactive lessons
Languages (JS, TS, Python, Java, C, C++)
Advanced Topics lessons
Advanced Topics time and space complexity compared
Best, average and worst-case running time and extra space for every advanced topics lesson, as each lesson derives them.
| Lesson | Best | Average | Worst | Space |
|---|---|---|---|---|
| Introduction | Varies | Varies | Varies | Varies |
| Introduction | O(1) (Peek) | O(log N) (Insert/Delete) | O(log N) (Insert/Delete) | O(N) |
| Heap Operations | O(1) (Insert if no swim needed) | O(log N) | O(log N) | O(N) |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) |
| Introduction | O(1) | O(N) (Naive) | O(N) (Naive) | O(N) |
| Optimized Union-Find | O(α(N)) | O(α(N)) | O(α(N)) | O(N) |
| Introduction | O(N) | O(N log K) | O(N log K) | O(K) |
| Kth Largest Element | O(N) | O(N log K) | O(N log K) | O(K) |
| Introduction | O(N log N) | O(N log N) | O(N log N) | O(N) |
| Meeting Rooms II | O(N log N) | O(N log N) | O(N log N) | O(N) |
| Introduction | O((N+Q)*sqrt(N)) | O((N+Q)*sqrt(N)) | O((N+Q)*sqrt(N)) | O(N) |
| Mo's Algorithm | O((N+Q) * sqrt(N)) | O((N+Q) * sqrt(N)) | O((N+Q) * sqrt(N)) | O(N + Q) |
| Tries | O(1) | O(L) | O(L) | O(N*L) |
| Z-Algorithm | O(N) | O(N) | O(N) | O(N) |
| Suffix Array | Ω(N² log N) | Θ(N² log N) | O(N² log N) | O(N) to O(N²) |
| Bitmask DP | O(N * 2^N) | O(N^2 * 2^N) | O(N^2 * 2^N) | O(N * 2^N) |
| Matrix Exponentiation | O(k^3 log N) | O(k^3 log N) | O(k^3 log N) | O(k^2) |
Continue the DSA curriculum
Advanced Topics is one of 12 topics in the interactive DSA visualizer curriculum. Once this topic is comfortable, the coding interview pattern library reorganises the same material around the patterns interview questions are built on.
Every other DSA visualizer
Data Structures · 28 lessons
- StackFree
- QueueFree
- Deque
- Circular Queue
- Priority Queue (ADT)
- Tree Traversal
- Binary Tree
- Binary Search Tree
- AVL Tree
- Trie (Prefix Tree)
- Segment Tree
- Fenwick Tree
- Red-Black Tree
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Graph RepresentationFree
- Breadth First SearchFree
- Depth First Search
- Topological Sort
- Cycle Detection
- Connected Components
- Bipartite Graph
- Dijkstra's Algorithm
- Bellman-Ford Algorithm
- Minimum Spanning Tree
- Floyd-Warshall Algorithm
- Bridges & Articulation Points