This is a cheatsheet. Bookmark it, print it, tape it to the wall. The fastest way to solve interview problems isn’t memorizing solutions — it’s recognizing which pattern applies. Once we know the pattern, the solution flows naturally.
The Master Pattern Table
Quick Decision Flowchart
Not sure which pattern to use? Walk through this:
Pattern Selection Flowchart
1.
Is it about a sorted array or search space?
→ Binary Search. If "minimize the max" → Binary Search on Answer.
2.
Is it about a contiguous subarray or substring?
→ Sliding Window. If it involves sums → maybe Prefix Sum too.
3.
Is it about pairs in a sorted array?
→ Two Pointers.
4.
Is it about a tree or graph?
→ BFS for shortest path / level-order. DFS for everything else. Union-Find for connectivity.
5.
Does it say "all possible" or "generate all"?
→ Backtracking.
6.
Does it ask "how many ways" or "min/max cost"?
→ Dynamic Programming. Try greedy first -- if it fails, it's DP.
7.
Does it involve "next greater" or "next smaller"?
→ Monotonic Stack.
8.
Does it say "kth largest" or "top k"?
→ Heap / Priority Queue.
9.
Does it involve lookups, counting, or grouping?
→ Hash Map / Set. When in doubt, a hash map is almost always useful.
Common Combinations
Sometimes one pattern isn’t enough. Here are combos that show up frequently:
| Problem Type | Combo |
|---|---|
| Subarray sum equals k | Prefix Sum + Hash Map |
| Minimum window substring | Sliding Window + Hash Map |
| Meeting rooms II | Intervals + Sweep Line (or Heap) |
| Course schedule | Graph + Topological Sort (BFS/DFS) |
| Word search in grid | DFS + Backtracking |
| Kth smallest in sorted matrix | Binary Search + Heap |
| Accounts merge | Union-Find + Hash Map |
| Autocomplete with ranking | Trie + Heap |
Time Complexity Quick Reference
| Pattern | Typical Time | Typical Space |
|---|---|---|
| Two Pointers | O(n) | O(1) |
| Sliding Window | O(n) | O(k) |
| Hash Map | O(n) | O(n) |
| Prefix Sum | O(n) build, O(1) query | O(n) |
| Binary Search | O(log n) | O(1) |
| BFS/DFS | O(V + E) | O(V) |
| DP (1D) | O(n) | O(n) |
| DP (2D) | O(n * m) | O(n * m) |
| Backtracking | O(2^n) or O(n!) | O(n) |
| Heap operations | O(n log k) | O(k) |
| Union-Find | O(n * a(n)) | O(n) |
| Trie | O(L) per op | O(total chars) |
General Interview Tips for DSA
Before coding:
- Repeat the problem back to the interviewer. Make sure we understand edge cases.
- Ask about constraints. Array size tells us the expected complexity (n <= 10^5 means O(n log n) is fine, n <= 20 means O(2^n) might be expected).
- Walk through 1-2 examples by hand. This often reveals the pattern.
During coding:
- Start with brute force and optimize. Say “the brute force is O(n^2), but we can do better with…” Interviewers love hearing the thought process.
- Name variables clearly.
left,right,seen,result— noti,j,x,y. - Talk while we code. Silence is the enemy in interviews.
After coding:
- Trace through the code with a small example. Catch bugs before the interviewer does.
- State the time and space complexity without being asked.
- Mention edge cases: empty input, single element, all duplicates, negative numbers.
The meta-strategy:
- If stuck for more than 2 minutes, say so. “I’m considering a few approaches…” is better than awkward silence.
- If we recognize the pattern but can’t remember the exact implementation, describe the approach. Interviewers give partial credit for understanding.
- If the interviewer gives a hint, take it. Don’t fight it. They’re trying to help us succeed.
In simple language, the interviewer isn’t testing if we’ve memorized LeetCode solutions. They’re testing if we can break a problem down, pick the right tool, and implement it cleanly. The patterns above are our toolbox. The more we practice recognizing which tool fits, the faster we’ll solve new problems we’ve never seen before.