How do you choose the right data structure for a problem?

Question

Accepted Answer

Pick the structure whose **most frequent operations are cheapest** for your access pattern. Start by listing the operations you'll perform, estimate their frequency, then match them to a structure's strengths.

## A decision checklist

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Match operations to complexity

| Need | Best structure | Key op cost |
|---|---|---|
| Random access by index | dynamic array | O(1) |
| Lookup by key | hash map | O(1) avg |
| Sorted + range queries | balanced BST | O(log n) |
| Min/max repeatedly | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefix search | trie | O(L) |

## Example reasoning

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Why it matters

Choosing well is often the difference between an O(n) and an O(n²) solution — the single biggest lever on performance.

Interviewers test exactly this reasoning: they want to see you map requirements to operation costs, not memorize structures.

Random access by index	dynamic array	O(1)
Lookup by key	hash map	O(1) avg
Sorted + range queries	balanced BST	O(log n)
Min/max repeatedly	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefix search	trie	O(L)