Decision Atlas
You now know thirteen structures. The last lesson teaches one thing: the moment you read a problem, which structure should come to mind. Choosing is not guesswork. List the operations you need, then pick the structure that makes them cheapest.
The decision tree
Walk down this tree for any problem. After enough repetitions you will do it without the diagram.
Which of these is closest to the main action in your problem?
How to use the decision tree
It is not a table of correct answers. It is an order of questions: first ask what the main action is, then ask whether you need order, prefixes, or updates. Real problems often need a combination (LRU is a hash table plus a linked list; top k frequent elements is a hash table plus a heap). Choose each part first, then put them together.
Signal words: the problem is telling you
When these words appear in a LeetCode problem, the structure is announcing itself.
| Words in the problem | What it points to | Why |
|---|---|---|
| “Have I seen it”, “remove duplicates”, “how many times” | Hash table · Set | O(1) reads and writes. The standard way to spend memory to save time. |
| “Two sum”, “find the pair”, “the complement” | Hash table | Scan once and ask at each step whether the other half you need has already appeared. |
| “Top-K”, “k-th largest”, “extremes in a stream” | Heap | Do not sort everything if you only need the extremes. For the k largest, a min-heap of size k acts as the threshold. |
| “Brackets”, “nesting”, “undo”, “the nearest one” | Stack | Handling the most recent item first is exactly LIFO. |
| “Next greater element”, “next smaller element” | Monotonic stack | The moment a new element pops an old one, the answer for the popped element is known. |
| “Maximum or minimum inside a sliding window” | Monotonic deque | Both ends change, and this is the only O(n) solution for the extreme value in a window. |
| “Contiguous subarray”, “substring” | Sliding window / prefix sum | Keep a quantity inside the window that can be updated step by step. If a sum is involved, add a prefix sum array. |
| “Find x in a sorted array” | Binary search | Sorted plus random access means every step removes half of what is left. |
| “Remove in place”, “move elements” | Two pointers | Separate reading from writing. Everything left of slow is already arranged. |
| “The k-th node”, “a cycle”, “the middle node” | Fast and slow pointers | The gap in steps, or the difference in speed, is the answer. |
| “Prefix”, “autocomplete”, “starts with x” | Trie | A hash table cannot answer prefix questions. A trie shares prefixes along a path. |
| “Friend circles”, “merge islands”, “connected components” | Union-Find | You need the group, not the path. Merge and query both cost close to O(1). |
| “Prerequisites”, “dependencies”, “build order” | Topological sort | On a directed acyclic graph, repeatedly take the nodes whose in-degree is 0. |
| “Shortest path”, “fewest steps” | BFS / Dijkstra | On an unweighted graph, BFS finds the shortest path by construction. With weights, use Dijkstra. |
| “Range query plus sorted traversal” | BST / TreeMap | A red-black tree gives every operation in O(log n), and an in-order walk is already sorted. |
| “Range sum or minimum, and the data still changes” | Segment tree / Fenwick tree | A prefix sum array breaks down under updates. A divide-and-conquer tree handles both sides. |
| “Cache eviction”, “least recently used” | LRU: hash table + doubly linked list | The hash table finds the node and the list keeps the order of use. Two O(1) structures make one. |
The full complexity table
The complete version of the table from chapter 00. By now you can explain every cell.
| Structure | Access | Search | Insert | Delete | Space | Note |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) | Search is O(log n) if it is sorted. |
| Dynamic array | O(1) | O(n) | O(n) | O(n) | O(n) | Appending at the end is O(1) amortized. |
| Linked list | O(n) | O(n) | O(1) | O(1) | O(n) | O(1) insert and delete require holding the position already. |
| Stack | — | — | O(1) | O(1) | O(n) | Only the top is touched. |
| Queue / Deque | — | — | O(1) | O(1) | O(n) | Both ends are O(1). |
| Hash table | — | O(1) | O(1) | O(1) | O(n) | Average. Worst case is O(n). |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) if it degenerates. An in-order walk is sorted. |
| Heap | O(1) | O(n) | O(log n) | O(log n) | O(n) | Access means reading the top. Building from an array is O(n). |
| Trie | — | O(1) | O(1) | — | O(Σ|w|) | Cost is measured by the word length L. |
| Union-Find | — | O(1) | O(1) | — | O(n) | About O(α(n)), which is effectively O(1). |
| Graph (adjacency list) | — | — | O(1) | — | O(V+E) | A full traversal is O(V+E). |
| Segment tree / Fenwick tree | — | O(log n) | O(log n) | — | O(n) | Range query plus point update. |
All problems in the course: 127
Every problem from the thirteen chapters, sharing the same progress as the chapters themselves.
Where to go from here
Data structures are the nouns and algorithms are the verbs. You now hold all the nouns.
Continue along the threads this course started: the boundary variants of binary search (a rotated array, searching on the answer), then backtracking (the recursion tree you practised in the binary tree chapter), then greedy algorithms, then dynamic programming (you already wrote Kadane's algorithm, which is DP). Every topic builds on a structure you already have.
Scale the structures up by a factor of ten thousand: hashing becomes consistent hashing and sharding; a skip list becomes a Redis sorted set; a B+ tree becomes a database index; a Bloom filter protects a cache; a queue becomes Kafka. Every engineering callout in this course is an entry point.
Go back to the table in §04. Clear the Easy problems first, then work through the Medium ones under time pressure. After each problem, answer three questions: what is the complexity, why can it be improved, and what would change with a different data structure? Those three questions are what interviews test.
A week from now, retake the quiz in every chapter. A month from now, read only the key points card at the end of each chapter. The green dots in the sidebar keep the record for you. Forgetting is normal; the schedule of review is what matters.
Final quiz: 11 questions about choosing a structure
✎ Final quizNot definitions. Only choices. This is what an interview actually asks.
You have to check whether the brackets in a code editor are matched, with nesting allowed. Which structure fits?
A support system must always serve the user who has been waiting the longest. What do you choose?
A live game leaderboard shows only the top 100, and player scores keep streaming in. What do you choose?
In a social app, people keep adding each other as friends, and you must answer instantly whether A and B are in the same friend group. What do you choose?
Typing “app” in a search box must immediately suggest apple, application, and so on. What do you choose?
A trading system writes a large stream of trade prices and must also report the total volume in any time range at any moment. What do you choose?
A course system must produce a valid order to take courses, where courses have prerequisites. What do you use?
A grading system inserts new scores often and must also list the students who scored between 80 and 90. What do you choose?
A browser caches at most 50 pages and evicts the one that has not been used for the longest time. What is the best combination?
For the fewest steps through an unweighted maze, do you use BFS or DFS, and why?
Which of these statements are correct? (Select all that apply. This one covers the whole course.)
- Choosing takes three steps: list the operations you need, mark the most frequent one, then read the complexity table and pick the structure that makes it cheapest.
- Two physical facts run through everything: contiguous memory uses the base address + offset formula (arrays, hash buckets, heaps), and scattered memory uses references (linked lists, trees, graphs).
- Hard problems are built from parts: LRU is a hash table plus a doubly linked list; top k frequent elements is a hash table plus a heap; word search is a trie plus backtracking. Choose each part first, then combine them.
- No structure is best at everything. Every O(1) was paid for somewhere else. Being able to explain why you did not choose X is worth more in an interview than knowing how to use X.
- The end of this course is your starting point: work through the problem table three times and turn on every green dot. Then go and use it. 🎓