Data structure 12 of 12
Choosing a structure
You've met eleven structures. In an interview, picking the right one is often most of the solution. This page puts them side by side and gives you the few questions that decide.
A 3-minute conversation: Sam asks, Priya explains
- Sam Last lesson. Choosing between them?
- Priya In an interview, picking the right structure is often most of the solution. This page puts all eleven side by side, with the few questions that decide.
- Priya A carpenter doesn't ask "which tool can make a hole?" A hammer, a screwdriver and a saw all can, badly. They ask which tool does the job they do most often, fastest.
- Sam So what's the method?
- Priya List the operations your solution repeats inside the loop. Pick the structure that makes those cheap. Then check: the total is roughly how many times, times the cost each time.
- Sam What does the animation show?
- Priya The same job with two structures: counting repeats in nine numbers. The list compares each number with everything stored so far; the set looks in one bucket. Same answer, far less work.
- Sam And the big table?
- Priya Every structure with what it makes fast, what it makes slow, and when to reach for it. Arrays for positions. Maps for "seen, how many, where". Sets for membership. Stacks for the newest unfinished thing, queues for the oldest. Heaps for the smallest right now. Sorted maps for order. Graphs for connections.
- Sam The questions that decide?
- Priya Ask what your loop keeps asking. "What's at position i?" Array. "Have I seen this?" Set. "How many, or where?" Map. "Most recent unfinished?" Stack. "Oldest waiting?" Queue. "Smallest right now?" Heap. "Next bigger, or a range?" Sorted structure. "Who's connected?" Graph.
- Priya Your turn. Jobs arrive with priorities and you always run the most urgent next. Which structure?
- Priya A heap: push and pop the most urgent in logarithmic time.
- Sam The two comparisons?
- Priya Membership with a list versus a set, counting the comparisons each makes. And the smallest so far as items arrive, re-sorting versus a heap.
- Sam Memory hook?
- Priya Name the repeated question, then pick the structure that answers it in one step.
- Sam And the problem?
- Priya How many numbers are smaller than the current one. Comparing every pair is quadratic. Counting values in a small array and turning the counts into running totals makes every answer one lookup.
- Sam Mistakes?
- Priya "In" on a list inside a loop, the most common hidden quadratic. Sorting when you only need the top. A hash map when you need order. And over-engineering, when two variables would do.
- Sam So now the patterns?
- Priya Now the patterns. Each one is a recipe built from the structures you just learned. Start with twenty-one, array and string basics.
1. What it is
A workshop wall of tools. A hammer, a screwdriver and a saw can all, technically, make a hole in a plank. A good carpenter doesn't ask "which tool can do this?" but "which tool does the job I do most often, fastest?"
Every structure makes some operations cheap and others expensive. So the method is always the same:
- List the operations your solution does over and over (inside the loop): look up by position? check membership? take the smallest? add at the front?
- Pick the structure that makes those operations cheap.
- Check the cost: the total is roughly (how many times) × (cost of the operation).
2. The same job, two structures
The same task with two different structures. Finding whether any value repeats: scanning a list for each value costs up to n checks per value; a set answers each check in one step.
3. Every structure at a glance
| Structure | Fast (O(1) or O(log n)) | Slow (O(n)) | Reach for it when |
|---|---|---|---|
| Array / list | read or write by index; add or remove at the end | insert or remove at the front or middle; search | you need positions, or to walk in order |
| String | read by index; length | building with +=; every "change" | text; build with a list and join |
| Hash map | get, set, delete, contains by key | anything about order | "seen before?", "how many?", "where?" |
| Hash set | add, remove, contains | order; counts | membership; removing duplicates; visited |
| Linked list | insert or remove at the head or after a known node | reach the i-th item; search | constant-time splicing (LRU cache), or the input is one |
| Stack | push, pop, peek the newest | anything below the top | the most recent unfinished thing: nesting, undo, DFS |
| Queue / deque | add and remove at both ends | the middle | oldest first: BFS, processing in order, sliding windows |
| Heap | peek the smallest (O(1)); push, pop (O(log n)) | search; anything but the top | repeatedly take the smallest or largest; top k |
| Binary tree | reach a child | search (no order) | hierarchies; the input is one |
| BST / sorted map | search, insert, min, max, next bigger (O(log n) balanced) | — | you need order and fast updates |
| Graph (adjacency list) | neighbours of a node | "is there an edge?" (use a matrix or set) | connections: networks, dependencies, grids |
4. The questions that decide
The questions that decide, in the order to ask them:
| If the solution keeps asking… | Use |
|---|---|
| "What's at position i?" | an array |
| "Have I seen this?" | a hash set |
| "How many times? / where? / what goes with this?" | a hash map |
| "What's the most recent unfinished thing?" | a stack |
| "What's the oldest waiting thing?" | a queue |
| "What's the smallest (or largest) right now?" | a heap |
| "What's the next bigger value? / everything in this range?" | a sorted array (binary search) or a sorted map |
| "Who is connected to whom?" | a graph (adjacency list) |
5. Side by side, step by step
Two side-by-side comparisons: the same job done with a slow structure and a fast one.
A · Membership: a list scan versus a set
What it doesCounts duplicates in two ways: checking a list (slow) and checking a set (fast).
Picture itLooking for a friend in a crowd by checking every face, versus asking the door staff who has a stamp.
CostList:
O(n²) in total. Set: O(n).The code. Same logic, one changed line: seen = [] versus seen = set().
def repeats(nums, use_set):
seen = set() if use_set else []
count = 0
for x in nums:
if x in seen:
count += 1
elif use_set:
seen.add(x)
else:
seen.append(x)
return countfunction repeats(nums: number[], useSet: boolean): number {
const asSet = new Set<number>(), asList: number[] = [];
let count = 0;
for (const x of nums) {
if (useSet ? asSet.has(x) : asList.includes(x)) {
count += 1;
} else if (useSet) {
asSet.add(x);
} else {
asList.push(x);
}
}
return count;
}static int repeats(int[] nums, boolean useSet) {
Set<Integer> asSet = new HashSet<>(); List<Integer> asList = new ArrayList<>();
int count = 0;
for (int x : nums) {
if (useSet ? asSet.contains(x) : asList.contains(x)) {
count += 1;
} else if (useSet) {
asSet.add(x);
} else {
asList.add(x);
}
}
return count;
}Line by line.
| Line | What it does | Why |
|---|---|---|
seen = set() if use_set else [] | The only real difference. | Same answer; very different speed for large inputs. |
if x in seen | The repeated operation. | On a list it compares x with every element; on a set it's one bucket. |
Watch it run. [3, 1, 4, 1, 5, 9, 2, 6, 5], counting the comparisons each way.
Watch out for:
- Choosing by habit. A list is the default container, but "in" on a list inside a loop is the most common hidden O(n²).
B · Smallest so far: re-sorting versus a heap
What it doesItems arrive one by one; after each, report the smallest. Re-sorting each time versus a heap.
Picture itRe-alphabetising the whole bookshelf every time a book arrives, versus a pile where the lightest book is always on top.
CostRe-sorting:
O(n² log n) in total. Heap: O(n log n) (and peeking is O(1)).The code. Both give the same answers; count the work.
import heapq
def smallest_each_time(nums):
h = []
out = []
for x in nums:
heapq.heappush(h, x)
out.append(h[0])
return outfunction smallestEachTime(nums: number[]): number[] {
let best = Infinity;
const out: number[] = [];
for (const x of nums) {
best = Math.min(best, x);
out.push(best);
}
return out;
}static List<Integer> smallestEachTime(int[] nums) {
PriorityQueue<Integer> h = new PriorityQueue<>();
List<Integer> out = new ArrayList<>();
for (int x : nums) {
h.offer(x);
out.add(h.peek());
}
return out;
}Line by line.
| Line | What it does | Why |
|---|---|---|
heapq.heappush(h, x) | O(log n) per arrival. | No full sort: only one path of the tree changes. |
out.append(h[0]) | The smallest is always at index 0. | Peeking is O(1). |
Watch it run. [7, 4, 9, 2, 5] arriving one at a time.
Watch out for:
- Over-engineering. If you only ever need the smallest (no removals), a single variable is enough: that's what the TypeScript version does. Use a heap when items also leave.
6. How to remember it
Memory hook: "Name the repeated question"Find the question your loop asks over and over, then pick the structure that answers it in one step.
Picture
A tool wall, each tool labelled with the one job it does fastest.
Chant
"Position: array. Seen: set. Count: map. Newest: stack. Oldest: queue. Smallest: heap. Order: sorted. Links: graph."
Key rule
Total cost ≈ how many times × cost per time. Shrink the second factor.
7. Problems solved with it
One easy problem where the choice of structure is the whole solution.
LC 1365 · How Many Numbers Are Smaller Than the Current Number
The problemFor each
nums[i] (each between 0 and 100), count how many numbers in the array are smaller than it.What it doesCounts each value in a 101-slot array, turns it into running totals, then reads each answer in O(1).
Cost
O(n + 101), instead of O(n²) for comparing every pair.The code. The question "how many are smaller than v?" is asked n times, so make it a lookup.
def smaller_numbers(nums):
count = [0] * 102
for x in nums:
count[x + 1] += 1
for v in range(1, 102):
count[v] += count[v - 1]
return [count[x] for x in nums]function smallerNumbers(nums: number[]): number[] {
const count = new Array(102).fill(0);
for (const x of nums) {
count[x + 1] += 1;
}
for (let v = 1; v < 102; v++) {
count[v] += count[v - 1];
}
return nums.map((x) => count[x]);
}static int[] smallerNumbers(int[] nums) {
int[] count = new int[102];
for (int x : nums) {
count[x + 1] += 1;
}
for (int v = 1; v < 102; v++) {
count[v] += count[v - 1];
}
int[] out = new int[nums.length];
for (int i = 0; i < nums.length; i++) out[i] = count[nums[i]];
return out;
}Line by line.
| Line | What it does | Why |
|---|---|---|
count[x + 1] += 1 | Count each value, shifted one slot right. | After the running total, count[v] is how many values are below v. |
count[v] += count[v - 1] | Running totals. | The prefix-sum idea from the arrays page. |
[count[x] for x in nums] | Each answer is one lookup. |
Watch it run. [8, 1, 2, 2, 3].
Watch out for:
- Two nested loops. Fine for 5 numbers, O(n²) for 500.
More practice, solved on the pattern pages
| # | Problem | Level | Where |
|---|---|---|---|
| 1 | Two Sum | Easy | Solved step by step on 16 · Hash Map & Set |
| 20 | Valid Parentheses | Easy | Solved step by step on 17 · Stack |
| 1046 | Last Stone Weight | Easy | Solved step by step on 07 · Top 'K' Elements |
| 217 | Contains Duplicate | Easy | Solved step by step on 16 · Hash Map & Set |
| 637 | Average of Levels in Binary Tree | Easy | Solved step by step on 12 · Breadth-First Search (BFS) |
8. Common mistakes
"in" on a list inside a loopThe most common hidden O(n²). If you check membership repeatedly, build a set first.
Sorting when you only need the topSorting is O(n log n); a heap gives the top k in O(n log k), and a single pass gives the minimum in O(n).
A hash map when you need orderMaps don't keep keys sorted. Need the next bigger key? Sort, or use a sorted structure.
Over-engineeringSometimes two variables beat any structure (the smallest so far, the previous value). Use the simplest thing that makes the repeated operation cheap.
9. Self-check quiz
You must check, millions of times, whether a username is already taken.
Membership in O(1).
Check that every opening bracket is closed in the right order.
The most recently opened bracket must close first.
Jobs arrive with priorities; always run the most urgent next.
Push and pop the most urgent in O(log n).
Explore a maze level by level, nearest cells first.
Oldest first is breadth-first search.
Count how many times each word appears in a book.
Word → count.
Store meeting times and repeatedly ask "what's the next meeting after 2 pm?" while meetings are added.
The next key above x, with fast inserts.
10. Where it shows up next
You know the building blocks. Patterns are recipes that combine them; each pattern page names the structure it uses.
Start the patterns
21 · Array & String Basics, the first step of the beginner path.
See the whole path
The order to learn the 24 patterns: the beginner path.
Come back any time
The data structures overview links every page from this block.