📊 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 / ListO(1)O(n)O(n)*O(n)O(n)
Hash Map / Dict—O(1) avgO(1) avgO(1) avgO(n)
Set—O(1) avgO(1) avgO(1) avgO(n)
Stack—O(n)O(1)O(1)O(n)
Queue—O(n)O(1)O(1)O(n)
Linked ListO(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)
HeapO(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
OperationTimePython
Access by indexO(1)arr[i]
AppendO(1) amortizedarr.append(x)
Insert at iO(n)arr.insert(i, x)
Delete at iO(n)arr.pop(i)
SearchO(n)x in arr
SortO(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"
OperationTimePython
Get / SetO(1) avgd[key] = val
DeleteO(1) avgdel d[key]
Check keyO(1) avgkey in d
IterateO(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
OperationTimePython
AddO(1) avgs.add(x)
RemoveO(1) avgs.discard(x)
MembershipO(1) avgx in s
UnionO(n+m)s1 | s2
IntersectionO(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)
OperationTimePython
PushO(1)stack.append(x)
PopO(1)stack.pop()
PeekO(1)stack[-1]
Is emptyO(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)
OperationTimePython
Enqueue (right)O(1)q.append(x)
Dequeue (left)O(1)q.popleft()
Peek frontO(1)q[0]
Append leftO(1)q.appendleft(x)
BFS — Level Order Traversal Rotting Oranges Sliding Window Maximum Number of Islands (BFS)
queue_patterns.py read-only

🔗 Linked List

-o
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"
OperationTimeNotes
Access by indexO(n)Must traverse
Insert at headO(1)Adjust pointers
Insert at known nodeO(1)If you have the reference
Delete known nodeO(1)If you have prev pointer
SearchO(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
OperationTimeNotes
DFS traversalO(n)Visit every node
BFS traversalO(n)Level by level
HeightO(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
OperationTime (balanced)Time (worst)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
Min / MaxO(log n)O(n)
InorderO(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
OperationTimePython
Get minO(1)heap[0]
PushO(log n)heapq.heappush(h, x)
Pop minO(log n)heapq.heappop(h)
HeapifyO(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)

T
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"
OperationTimeNotes
Insert wordO(k)k = word length
Search wordO(k)Exact match
Prefix searchO(k)Starts-with check
SpaceO(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

G
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"
OperationAdj ListAdj Matrix
Add edgeO(1)O(1)
Check edgeO(degree)O(1)
All neighborsO(degree)O(V)
BFS / DFSO(V + E)O(V^2)
SpaceO(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
🤖 AI-first 🎓 Placement Assistance

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 →