DSA Cheat Sheet
Big-O complexities, algorithm patterns, sorting comparisons, and interview tips — all on one page.
Data Structure Complexity
| Structure | Access | Insert | Delete | Space | Notes |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Contiguous memory, cache-friendly |
| Linked List | O(n) | O(1)* | O(n) | O(n) | *O(1) insert if you have the node ref |
| Hash Map | O(1) avg | O(1) avg | O(1) avg | O(n) | Amortized; worst case O(n) with collisions |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | Balanced: AVL, Red-Black guarantee O(log n) |
| Heap / Priority Queue | O(1) peek | O(log n) | O(log n) | O(n) | Min-heap or max-heap; used in top-K, Dijkstra |
| Stack | O(1) | O(1) | O(1) | O(n) | LIFO; used in DFS, expression eval, monotonic patterns |
| Queue | O(1) | O(1) | O(1) | O(n) | FIFO; used in BFS, sliding window |
| Trie | O(L) | O(L) | O(L) | O(N*L) | L = word length; prefix search, autocomplete |
| Graph (Adj List) | O(V+E) | O(1) | O(V) | O(V+E) | BFS/DFS traversal; sparse graphs preferred |
10 Must-Know Algorithm Patterns
Recognizing patterns is the single most important skill for coding interviews. Each pattern below includes when to use it, classic problems, and a pseudocode template.
Two Pointers
When: Array sorted or pair-sum problems
Classic problems: Two Sum II, Container With Most Water, 3Sum
for left=0, right=n-1: shrink based on comparisonSliding Window
When: Subarray/substring with constraint (max, min, distinct)
Classic problems: Longest Substring Without Repeating, Min Window Substring
expand right, shrink left when constraint violatedBinary Search
When: Sorted array, search space with monotonic property
Classic problems: Search in Rotated Array, Koko Eating Bananas
lo, hi = bounds; mid = (lo+hi)//2; adjust based on conditionBFS / Level-order
When: Shortest path (unweighted), level-by-level tree traversal
Classic problems: Binary Tree Level Order, Rotting Oranges, Word Ladder
queue = deque([start]); process level by levelDFS / Backtracking
When: All paths, permutations, combinations, constraint satisfaction
Classic problems: Subsets, Permutations, N-Queens, Word Search
choose → explore → unchoose; prune earlyDynamic Programming
When: Overlapping subproblems + optimal substructure
Classic problems: Climbing Stairs, Longest Common Subsequence, Coin Change
dp[i] = f(dp[i-1], dp[i-2], ...); bottom-up or memoized top-downMonotonic Stack
When: Next greater/smaller element, histogram problems
Classic problems: Daily Temperatures, Largest Rectangle in Histogram
maintain decreasing/increasing stack; pop when violatedTopological Sort
When: DAG ordering, dependency resolution, course scheduling
Classic problems: Course Schedule, Alien Dictionary
Kahn's (BFS + in-degree) or DFS post-order reversalUnion-Find
When: Connected components, cycle detection, grouping
Classic problems: Number of Islands, Redundant Connection, Accounts Merge
find(x) with path compression, union by rankGreedy
When: Local optimal leads to global optimal; interval scheduling
Classic problems: Jump Game, Merge Intervals, Task Scheduler
sort by end time / deadline; process greedilySorting Algorithm Comparison
| Algorithm | Best | Worst | Space | Stable? | Notes |
|---|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes | Educational only |
| Selection Sort | O(n²) | O(n²) | O(1) | No | Minimal swaps |
| Insertion Sort | O(n) | O(n²) | O(1) | Yes | Best for nearly sorted |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | Stable, predictable |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No | Fast in practice; partition-based |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No | In-place, not stable |
| Counting Sort | O(n+k) | O(n+k) | O(k) | Yes | k = range; integer keys only |
| Radix Sort | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | Yes | d = digits; non-comparison |
Big-O Complexity Hierarchy
From fastest to slowest growth. For n = 1,000,000:
Interview Quick Tips
Before Coding
- Clarify inputs, outputs, edge cases
- Ask about constraints (n size, duplicates, sorted?)
- Walk through 1-2 examples out loud
- State your approach + time complexity BEFORE coding
While Coding
- Use meaningful variable names
- Talk through your logic as you write
- Handle edge cases (empty, single element, overflow)
- Don't optimize prematurely — get a working solution first
After Coding
- Trace through with a test case
- State time and space complexity
- Discuss trade-offs and potential optimizations
- Ask if the interviewer wants you to optimize
Common Mistakes
- Jumping to code without understanding the problem
- Off-by-one errors in loops and indices
- Forgetting to handle null / empty inputs
- Not considering integer overflow for large inputs
Ready to Practice?
Apply these patterns to 57+ curated problems with Java solutions.