| Data Structure |
Access |
Search |
Insert |
Delete |
Space |
Notes |
| Array |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
Insert/delete at end is O(1) amortized |
| Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Insert/delete O(1) with reference to node |
| Doubly Linked List |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Used in LRU cache with HashMap |
| Stack |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
LIFO — push/pop are O(1) |
| Queue |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
FIFO — enqueue/dequeue are O(1) |
| Deque |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
Both ends O(1). Monotonic deque for sliding window |
| Hash Map |
O(1)* |
O(1)* |
O(1)* |
O(1)* |
O(n) |
*Amortized. Worst case O(n) with collisions |
| Hash Set |
— |
O(1)* |
O(1)* |
O(1)* |
O(n) |
*Amortized. Great for membership testing |
| BST (balanced) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Unbalanced degrades to O(n) |
| Red-Black / AVL Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Self-balancing. TreeMap/TreeSet in Java |
| Min/Max Heap |
O(1) top |
O(n) |
O(log n) |
O(log n) |
O(n) |
PriorityQueue in Java/Kotlin. Top-K, median |
| Trie |
— |
O(k) |
O(k) |
O(k) |
O(n·k) |
k = key length. Autocomplete, prefix search |
| Union-Find |
— |
O(α(n))≈O(1) |
O(α(n))≈O(1) |
— |
O(n) |
With path compression + union by rank |
| Segment Tree |
O(log n) |
O(log n) |
O(log n) |
— |
O(n) |
Range queries + point updates |
| Bloom Filter |
— |
O(k) |
O(k) |
— |
O(m) |
Probabilistic. False positives, no false negatives |
| Algorithm |
Best |
Average |
Worst |
Space |
Stable? |
When to Use |
| Quick Sort |
O(n log n) |
O(n log n) |
O(n²) |
O(log n) |
No |
Default general purpose. In-place |
| Merge Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Yes |
Stable sort needed. Linked lists. External sort |
| Heap Sort |
O(n log n) |
O(n log n) |
O(n log n) |
O(1) |
No |
Guaranteed O(n log n), in-place |
| Tim Sort |
O(n) |
O(n log n) |
O(n log n) |
O(n) |
Yes |
Java/Kotlin/Python default. Real-world data |
| Counting Sort |
O(n+k) |
O(n+k) |
O(n+k) |
O(k) |
Yes |
Small integer range. k = range of values |
| Radix Sort |
O(n·d) |
O(n·d) |
O(n·d) |
O(n+k) |
Yes |
Fixed-length integers/strings. d = digits |
| Bucket Sort |
O(n+k) |
O(n+k) |
O(n²) |
O(n) |
Yes |
Uniformly distributed data |
| Insertion Sort |
O(n) |
O(n²) |
O(n²) |
O(1) |
Yes |
Small/nearly sorted arrays. Online sorting |
| Algorithm |
Time |
Space |
Use Case |
| BFS |
O(V + E) |
O(V) |
Shortest path (unweighted), level-order, nearest |
| DFS |
O(V + E) |
O(V) |
Connected components, cycle detection, paths |
| Topological Sort (Kahn's) |
O(V + E) |
O(V) |
Task scheduling, dependency ordering, course schedule |
| Dijkstra's |
O((V+E) log V) |
O(V) |
Shortest path (non-negative weights) |
| Bellman-Ford |
O(V · E) |
O(V) |
Shortest path with negative weights |
| Floyd-Warshall |
O(V³) |
O(V²) |
All-pairs shortest path |
| Union-Find |
O(V · α(V)) |
O(V) |
Connected components, cycle detection (undirected) |
| Kruskal's (MST) |
O(E log E) |
O(V) |
Minimum spanning tree |
| Prim's (MST) |
O((V+E) log V) |
O(V) |
Minimum spanning tree (dense graphs) |
| Pattern |
Time |
Space |
Classic Problems |
| 1D DP |
O(n) |
O(1)–O(n) |
Fibonacci, climbing stairs, house robber, max subarray |
| 2D DP |
O(n·m) |
O(n·m) |
Edit distance, LCS, unique paths, knapsack |
| Interval DP |
O(n²)–O(n³) |
O(n²) |
Burst balloons, matrix chain, palindrome partitioning |
| Bitmask DP |
O(2ⁿ · n) |
O(2ⁿ) |
TSP, assignment problem, subset problems |
| Tree DP |
O(n) |
O(n) |
Max path sum, diameter, house robber III |
| Knapsack (0/1) |
O(n·W) |
O(W) |
Subset sum, partition equal subset, target sum |
| Unbounded Knapsack |
O(n·W) |
O(W) |
Coin change, rod cutting |
| LIS |
O(n log n) |
O(n) |
Longest increasing subsequence (patience sort) |
| Pattern |
Typical Complexity |
Key Data Structure |
Recognize When... |
| Sliding Window |
O(n) |
HashMap, Deque |
Contiguous subarray/substring, "at most K" |
| Two Pointers |
O(n) |
Array |
Sorted input, pair finding, palindrome |
| Fast & Slow Pointers |
O(n) |
Linked List |
Cycle detection, middle of list, happy number |
| Merge Intervals |
O(n log n) |
Array (sort first) |
Overlapping intervals, meeting rooms |
| Monotonic Stack |
O(n) |
Stack |
Next greater/smaller element, histogram area |
| Monotonic Deque |
O(n) |
Deque |
Sliding window max/min |
| Top-K Elements |
O(n log k) |
Min-Heap (size k) |
"K largest", "K most frequent", "K closest" |
| K-Way Merge |
O(n log k) |
Min-Heap |
Merge K sorted lists/arrays |
| Binary Search |
O(log n) |
Array |
Sorted data, "minimum that satisfies", rotated array |
| Backtracking |
O(2ⁿ) or O(n!) |
Recursion + pruning |
Permutations, combinations, subsets, N-queens |
| BFS (Level-order) |
O(V + E) |
Queue |
Shortest path, level traversal, word ladder |
| DFS + Memo |
Varies |
HashMap |
Overlapping subproblems, top-down DP |
| Union-Find |
O(n · α(n)) |
Array |
Connected components, "is connected", groups |
| Prefix Sum |
O(1) query |
Array |
Range sum queries, subarray sum equals K |
| Collection |
get/contains |
add/put |
remove |
Ordered? |
Notes |
ArrayList |
O(1) index |
O(1)* |
O(n) |
Insert order |
*Amortized. Remove from end O(1) |
LinkedList |
O(n) |
O(1) |
O(1) |
Insert order |
With iterator reference. Also implements Deque |
HashMap / mutableMapOf |
O(1)* |
O(1)* |
O(1)* |
No |
*Amortized. Most common in interviews |
LinkedHashMap |
O(1)* |
O(1)* |
O(1)* |
Insert order |
LRU cache with removeEldestEntry |
TreeMap / sortedMapOf |
O(log n) |
O(log n) |
O(log n) |
Sorted by key |
Red-Black tree. floorKey, ceilingKey |
HashSet / mutableSetOf |
O(1)* |
O(1)* |
O(1)* |
No |
Membership testing |
TreeSet / sortedSetOf |
O(log n) |
O(log n) |
O(log n) |
Sorted |
floor(), ceiling(), first(), last() |
PriorityQueue |
O(1) peek |
O(log n) |
O(log n) |
Heap order |
Min-heap by default. remove(obj) is O(n) |
ArrayDeque |
O(n) |
O(1)* |
O(1)* |
Insert order |
Faster than LinkedList as stack/queue |
| Trap |
What It Looks Like |
Actual Complexity |
| String concatenation in loop |
s += char in a loop |
O(n²) — strings are immutable, each concat copies. Use StringBuilder |
| List.contains() in loop |
if (list.contains(x)) in a loop |
O(n²) — use HashSet for O(1) lookup |
| Sorting inside loop |
Sort array, then loop and re-sort |
O(n² log n) — sort once, or use heap |
| HashMap with list values |
map[key] = map[key]!! + listOf(v) |
O(n²) — appending to immutable list copies. Use mutableListOf |
| Substring in Java |
s.substring(i, j) |
O(n) — creates new string (since Java 7u6) |
| PriorityQueue.remove(obj) |
pq.remove(element) |
O(n) — linear scan. poll() is O(log n) |
| Recursive Fibonacci |
fib(n-1) + fib(n-2) |
O(2ⁿ) — without memoization. With memo: O(n) |
| Generating all subsets |
Power set / backtracking |
O(2ⁿ) — inherently exponential, can't optimize |
| If You See... |
Think... |
Examples |
| Single pass through array |
O(n) |
Two pointers, sliding window, linear scan |
| Sort then scan |
O(n log n) |
Merge intervals, meeting rooms |
| Divide in half each step |
O(log n) |
Binary search, balanced BST lookup |
| Nested loops over same array |
O(n²) |
Brute force pair finding, bubble sort |
| Heap with K elements |
O(n log k) |
Top-K, K-way merge |
| Recursion with 2 branches |
O(2ⁿ) |
Subsets, naive Fibonacci (add memo!) |
| Recursion with N branches |
O(n!) |
Permutations, N-queens |
| Fill a 2D table |
O(n·m) |
Edit distance, LCS, grid DP |
| HashMap lookups in a loop |
O(n) |
Two sum, group anagrams, frequency count |
| BFS/DFS over graph |
O(V + E) |
Connected components, shortest path, islands |