📊 Master Big O Table
Every data structure at a glance. Bookmark this table — it covers 95% of what interviewers expect you to know about time complexity.
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array / List | O(1) | O(n) | O(n)* | O(n) | O(n) |
| Hash Map / Dict | — | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Set | — | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Stack | — | O(n) | O(1) | O(1) | O(n) |
| Queue | — | O(n) | O(1) | O(1) | O(n) |
| Linked List | O(n) | O(n) | O(1)** | O(1)** | O(n) |
| Binary Tree | — | O(n) | O(n) | O(n) | O(n) |
| BST (balanced) | — | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1)*** | O(n) | O(log n) | O(log n) | O(n) |
| Trie | — | O(k) | O(k) | O(k) | O(n*k) |
| Graph (adj list) | — | O(V+E) | O(1) | O(E) | O(V+E) |
* Append is amortized O(1). ** At known position. *** Min/max only. k = key length. V = vertices, E = edges.
📦 Array / List
Python: list
The default go-to data structure
When to use:
- You need O(1) access by index — the problem says "at position i"
- You need to iterate in order or use two pointers / sliding window
- The problem involves sorting, prefix sums, or binary search on sorted data
| Operation | Time | Python |
|---|---|---|
| Access by index | O(1) | arr[i] |
| Append | O(1) amortized | arr.append(x) |
| Insert at i | O(n) | arr.insert(i, x) |
| Delete at i | O(n) | arr.pop(i) |
| Search | O(n) | x in arr |
| Sort | O(n log n) | arr.sort() |
Two Sum
Best Time to Buy/Sell Stock
Maximum Subarray
Product of Array Except Self
Merge Intervals
array_basics.py read-only
#️⃣ Hash Map / Dict
Python: dict, collections.Counter, defaultdict
O(1) lookup — the interview MVP
When to use:
- You need O(1) key-value lookup — "find a pair", "count occurrences", "group by"
- You need to replace a nested loop with a single-pass solution
- The problem says "frequency", "anagram", "two sum", or "subarray sum equals k"
| Operation | Time | Python |
|---|---|---|
| Get / Set | O(1) avg | d[key] = val |
| Delete | O(1) avg | del d[key] |
| Check key | O(1) avg | key in d |
| Iterate | O(n) | for k, v in d.items() |
Two Sum
Group Anagrams
Subarray Sum Equals K
LRU Cache
Top K Frequent Elements
hashmap_patterns.py read-only
🔵 Set
Python: set, frozenset
Fast membership + uniqueness
When to use:
- You need O(1) membership checks without storing values — "does X exist?"
- You need to remove duplicates or track visited nodes
- The problem involves intersection, union, or difference of collections
| Operation | Time | Python |
|---|---|---|
| Add | O(1) avg | s.add(x) |
| Remove | O(1) avg | s.discard(x) |
| Membership | O(1) avg | x in s |
| Union | O(n+m) | s1 | s2 |
| Intersection | O(min(n,m)) | s1 & s2 |
Contains Duplicate
Longest Consecutive Sequence
Intersection of Two Arrays
Happy Number
set_patterns.py read-only
📚 Stack
Python: list (append/pop)
LIFO — Last In, First Out
When to use:
- You need to match or balance things — parentheses, brackets, HTML tags
- The problem involves nearest smaller/greater element (monotonic stack)
- You need to reverse something or undo operations (DFS backtracking)
| Operation | Time | Python |
|---|---|---|
| Push | O(1) | stack.append(x) |
| Pop | O(1) | stack.pop() |
| Peek | O(1) | stack[-1] |
| Is empty | O(1) | not stack |
Valid Parentheses
Min Stack
Daily Temperatures
Largest Rectangle in Histogram
Evaluate Reverse Polish Notation
stack_patterns.py read-only
🚶 Queue
Python: collections.deque
FIFO — First In, First Out
When to use:
- You need BFS — level-order tree traversal, shortest path in unweighted graph
- The problem says "nearest", "shortest", or "minimum steps" in a grid/graph
- You need a sliding window max/min (monotonic deque)
| Operation | Time | Python |
|---|---|---|
| Enqueue (right) | O(1) | q.append(x) |
| Dequeue (left) | O(1) | q.popleft() |
| Peek front | O(1) | q[0] |
| Append left | O(1) | q.appendleft(x) |
BFS — Level Order Traversal
Rotting Oranges
Sliding Window Maximum
Number of Islands (BFS)
queue_patterns.py read-only
🔗 Linked List
Python: custom Node class
Dynamic size, O(1) insert/delete at known position
When to use:
- You need O(1) insert/delete at a known node — no shifting like arrays
- The problem involves cycle detection (Floyd's tortoise and hare)
- The problem says "merge two sorted lists", "reverse a list", or "find the middle node"
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(n) | Must traverse |
| Insert at head | O(1) | Adjust pointers |
| Insert at known node | O(1) | If you have the reference |
| Delete known node | O(1) | If you have prev pointer |
| Search | O(n) | Linear scan |
Reverse Linked List
Merge Two Sorted Lists
Linked List Cycle
Remove Nth Node From End
LRU Cache
linkedlist_patterns.py read-only
🌲 Binary Tree
Python: custom TreeNode class
Hierarchical data, recursive traversals
When to use:
- The problem explicitly says "given a binary tree" — traversals, depth, paths
- You need to explore all paths or compute properties recursively (height, diameter, subtree sums)
- The problem asks for inorder, preorder, postorder, or level-order traversal
| Operation | Time | Notes |
|---|---|---|
| DFS traversal | O(n) | Visit every node |
| BFS traversal | O(n) | Level by level |
| Height | O(n) | Recursive |
| Search (unordered) | O(n) | Must check all |
Maximum Depth
Invert Binary Tree
Diameter of Binary Tree
Lowest Common Ancestor
Serialize/Deserialize
binary_tree_patterns.py read-only
🔍 Binary Search Tree
Python: custom or sortedcontainers.SortedList
Sorted data with O(log n) operations
When to use:
- You need data that stays sorted with efficient insert/delete/search — all O(log n)
- The problem asks for kth smallest, range queries, or inorder successor
- Key insight: inorder traversal of a BST gives sorted order
| Operation | Time (balanced) | Time (worst) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min / Max | O(log n) | O(n) |
| Inorder | O(n) | O(n) |
Validate BST
Kth Smallest Element
Lowest Common Ancestor in BST
Convert Sorted Array to BST
bst_patterns.py read-only
⛰️ Heap / Priority Queue
Python: heapq (min-heap)
Fast min/max extraction
When to use:
- You need the k largest/smallest elements — "top K", "kth largest"
- You need to repeatedly extract the minimum or maximum
- The problem involves merge K sorted lists, median from stream, or Dijkstra's algorithm
| Operation | Time | Python |
|---|---|---|
| Get min | O(1) | heap[0] |
| Push | O(log n) | heapq.heappush(h, x) |
| Pop min | O(log n) | heapq.heappop(h) |
| Heapify | O(n) | heapq.heapify(lst) |
Python only has min-heap.
For a max-heap, negate values: push -val, pop and negate back. Or use heapq.nlargest(k, iterable).
Kth Largest Element
Top K Frequent Elements
Merge K Sorted Lists
Find Median from Data Stream
Task Scheduler
heap_patterns.py read-only
🔤 Trie (Prefix Tree)
Python: dict of dicts (or custom TrieNode)
Prefix-based string operations in O(k)
When to use:
- The problem involves prefix search — autocomplete, spell checker, "starts with"
- You need to search among many strings sharing common prefixes
- The problem says "word search", "word dictionary", or "longest common prefix"
| Operation | Time | Notes |
|---|---|---|
| Insert word | O(k) | k = word length |
| Search word | O(k) | Exact match |
| Prefix search | O(k) | Starts-with check |
| Space | O(n * k) | n words, avg length k |
Implement Trie
Word Search II
Design Add and Search Words
Longest Common Prefix
trie_patterns.py read-only
🕸️ Graph
Python: dict (adjacency list), or list of lists
Relationships between entities
When to use:
- The problem models relationships — social networks, courses with prerequisites, routes between cities
- You see a grid — treat each cell as a node with 4 neighbors (up, down, left, right)
- The problem says "connected components", "shortest path", "topological order", or "cycle detection"
| Operation | Adj List | Adj Matrix |
|---|---|---|
| Add edge | O(1) | O(1) |
| Check edge | O(degree) | O(1) |
| All neighbors | O(degree) | O(V) |
| BFS / DFS | O(V + E) | O(V^2) |
| Space | O(V + E) | O(V^2) |
Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Dijkstra's Shortest Path
graph_patterns.py read-only
🧭 When to Use Which? Decision Flowchart
Use this flowchart during interviews to quickly narrow down the right data structure. Start at the top and follow the arrows.
What does the problem need?
Need O(1) lookup by key?
→
Hash Map / Set
Need O(1) access by index?
→
Array / List
Need LIFO (undo, matching, nesting)?
→
Stack
Need FIFO or BFS (shortest path)?
→
Queue / Deque
Need sorted data + fast insert/delete?
→
BST / Sorted Array
Need top-K or repeated min/max extraction?
→
Heap
Need prefix search among strings?
→
Trie
Need O(1) insert/delete at known position?
→
Linked List
Modeling relationships or connections?
→
Graph
Hierarchical / recursive structure?
→
Binary Tree
Combination patterns are common.
Many interview problems use two structures together: hash map + linked list (LRU Cache), heap + hash map (Top K Frequent), graph + heap (Dijkstra), trie + DFS (Word Search II). When one structure is not enough, ask: "What operation is still slow? What structure speeds it up?"
🐍 Python Quick Imports
Copy-paste these at the top of your interview code. Know what each one does before you use it.
python_imports.py read-only
Africa & India's Best AI Academy
Know your data structures.
Now land the job.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →