🧠 DSA Interview Prep — Pattern by Pattern

[shaishab316]

Goal: Crack FAANG/product company interviews by mastering patterns, not memorizing problems.
Track progress by checking off each problem as you solve it.

---

⚡ Pattern 1 — Arrays & Hashing

Key Idea: Use HashMaps/Sets for O(1) lookup. Think frequency count, index map, dedup.

• 1 · Two Sum — Easy
• 217 · Contains Duplicate — Easy
• 242 · Valid Anagram — Easy
• 49 · Group Anagrams — Medium
• 347 · Top K Frequent Elements — Medium
• 238 · Product of Array Except Self — Medium
• 36 · Valid Sudoku — Medium
• 128 · Longest Consecutive Sequence — Medium

---

👆 Pattern 2 — Two Pointers

Key Idea: Use left/right pointers on sorted arrays. Shrink the window based on condition.

• 125 · Valid Palindrome — Easy
• 26 · Remove Duplicates from Sorted Array — Easy
• 167 · Two Sum II — Medium
• 15 · 3Sum — Medium
• 11 · Container With Most Water — Medium
• 42 · Trapping Rain Water — Hard

---

🪟 Pattern 3 — Sliding Window

Key Idea: Expand right, shrink left. Track state (max, count, freq) inside the window.

• 121 · Best Time to Buy and Sell Stock — Easy
• 3 · Longest Substring Without Repeating Characters — Medium
• 424 · Longest Repeating Character Replacement — Medium
• 567 · Permutation in String — Medium
• 76 · Minimum Window Substring — Hard
• 239 · Sliding Window Maximum — Hard

---

📚 Pattern 4 — Stack

Key Idea: Use stack for next greater/smaller element, nested structures, monotonic problems.

• 20 · Valid Parentheses — Easy
• 155 · Min Stack — Medium
• 150 · Evaluate Reverse Polish Notation — Medium
• 22 · Generate Parentheses — Medium
• 739 · Daily Temperatures — Medium
• 853 · Car Fleet — Medium
• 84 · Largest Rectangle in Histogram — Hard

---

🔍 Pattern 5 — Binary Search

Key Idea: Eliminate half the search space each step. Works on sorted arrays and monotonic functions.

• 704 · Binary Search — Easy
• 74 · Search a 2D Matrix — Medium
• 875 · Koko Eating Bananas — Medium
• 153 · Find Minimum in Rotated Sorted Array — Medium
• 33 · Search in Rotated Sorted Array — Medium
• 981 · Time Based Key-Value Store — Medium
• 4 · Median of Two Sorted Arrays — Hard

---

🔗 Pattern 6 — Linked List

Key Idea: Use dummy nodes, fast/slow pointers, and in-place reversal techniques.

• 206 · Reverse Linked List — Easy
• 21 · Merge Two Sorted Lists — Easy
• 141 · Linked List Cycle — Easy
• 143 · Reorder List — Medium
• 19 · Remove Nth Node From End of List — Medium
• 138 · Copy List with Random Pointer — Medium
• 2 · Add Two Numbers — Medium
• 287 · Find the Duplicate Number — Medium
• 146 · LRU Cache — Medium
• 23 · Merge K Sorted Lists — Hard
• 25 · Reverse Nodes in K-Group — Hard

---

🌲 Pattern 7 — Trees (DFS / BFS)

Key Idea: Recursive DFS for path/depth problems. BFS (queue) for level-order traversal.

• 226 · Invert Binary Tree — Easy
• 104 · Maximum Depth of Binary Tree — Easy
• 543 · Diameter of Binary Tree — Easy
• 110 · Balanced Binary Tree — Easy
• 100 · Same Tree — Easy
• 572 · Subtree of Another Tree — Easy
• 102 · Binary Tree Level Order Traversal — Medium
• 199 · Binary Tree Right Side View — Medium
• 1448 · Count Good Nodes in Binary Tree — Medium
• 98 · Validate Binary Search Tree — Medium
• 235 · Lowest Common Ancestor of BST — Medium
• 124 · Binary Tree Maximum Path Sum — Hard
• 297 · Serialize and Deserialize Binary Tree — Hard

---

🔺 Pattern 8 — Heap / Priority Queue

Key Idea: Use min/max heap for top-K problems and streaming median.

• 703 · Kth Largest Element in a Stream — Easy
• 1046 · Last Stone Weight — Easy
• 973 · K Closest Points to Origin — Medium
• 215 · Kth Largest Element in an Array — Medium
• 621 · Task Scheduler — Medium
• 355 · Design Twitter — Medium
• 295 · Find Median from Data Stream — Hard

---

🔄 Pattern 9 — Backtracking

Key Idea: Build solution incrementally, prune invalid branches early, restore state on undo.

• 78 · Subsets — Medium
• 39 · Combination Sum — Medium
• 46 · Permutations — Medium
• 90 · Subsets II — Medium
• 40 · Combination Sum II — Medium
• 79 · Word Search — Medium
• 131 · Palindrome Partitioning — Medium
• 17 · Letter Combinations of a Phone Number — Medium
• 51 · N-Queens — Hard

---

🗺️ Pattern 10 — Graphs (DFS / BFS)

Key Idea: Track visited nodes. DFS for connected components, BFS for shortest path.

• 200 · Number of Islands — Medium
• 133 · Clone Graph — Medium
• 695 · Max Area of Island — Medium
• 417 · Pacific Atlantic Water Flow — Medium
• 130 · Surrounded Regions — Medium
• 994 · Rotting Oranges — Medium
• 286 · Walls and Gates — Medium
• 207 · Course Schedule — Medium
• 210 · Course Schedule II — Medium
• 684 · Redundant Connection — Medium
• 323 · Number of Connected Components — Medium
• 261 · Graph Valid Tree — Medium
• 127 · Word Ladder — Hard

---

🏔️ Pattern 11 — Advanced Graphs

Key Idea: Dijkstra for weighted shortest path, Topological sort for DAGs, Union-Find for connectivity.

• 332 · Reconstruct Itinerary — Hard
• 1584 · Min Cost to Connect All Points — Medium
• 743 · Network Delay Time — Medium
• 778 · Swim in Rising Water — Hard
• 269 · Alien Dictionary — Hard
• 787 · Cheapest Flights Within K Stops — Medium

---

🧩 Pattern 12 — Dynamic Programming (1D)

Key Idea: Break into subproblems. Cache results. Think: "What decision do I make at each step?"

• 70 · Climbing Stairs — Easy
• 746 · Min Cost Climbing Stairs — Easy
• 198 · House Robber — Medium
• 213 · House Robber II — Medium
• 5 · Longest Palindromic Substring — Medium
• 647 · Palindromic Substrings — Medium
• 91 · Decode Ways — Medium
• 322 · Coin Change — Medium
• 152 · Maximum Product Subarray — Medium
• 139 · Word Break — Medium
• 300 · Longest Increasing Subsequence — Medium
• 416 · Partition Equal Subset Sum — Medium

---

🧩 Pattern 13 — Dynamic Programming (2D)

Key Idea: Use 2D table. Classic: grid paths, edit distance, knapsack, string matching.

• 62 · Unique Paths — Medium
• 1143 · Longest Common Subsequence — Medium
• 309 · Best Time to Buy/Sell Stock with Cooldown — Medium
• 518 · Coin Change II — Medium
• 494 · Target Sum — Medium
• 97 · Interleaving String — Medium
• 329 · Longest Increasing Path in Matrix — Hard
• 115 · Distinct Subsequences — Hard
• 72 · Edit Distance — Hard
• 312 · Burst Balloons — Hard
• 10 · Regular Expression Matching — Hard

---

🌿 Pattern 14 — Greedy

Key Idea: Make the locally optimal choice at each step. Prove it leads to global optimum.

• 53 · Maximum Subarray — Medium
• 55 · Jump Game — Medium
• 45 · Jump Game II — Medium
• 134 · Gas Station — Medium
• 846 · Hand of Straights — Medium
• 1899 · Merge Triplets to Form Target — Medium
• 763 · Partition Labels — Medium
• 678 · Valid Parenthesis String — Medium

---

🔢 Pattern 15 — Intervals

Key Idea: Sort by start. Merge overlapping. Use sweep line for complex cases.

• 57 · Insert Interval — Medium
• 56 · Merge Intervals — Medium
• 435 · Non Overlapping Intervals — Medium
• 252 · Meeting Rooms — Easy
• 253 · Meeting Rooms II — Medium
• 1851 · Minimum Interval to Include Each Query — Hard

---

🔠 Pattern 16 — Tries

Key Idea: Prefix tree for fast string lookup, autocomplete, and prefix matching problems.

• 208 · Implement Trie (Prefix Tree) — Medium
• 211 · Design Add and Search Words Data Structure — Medium
• 212 · Word Search II — Hard

---

🧮 Pattern 17 — Bit Manipulation

Key Idea: XOR cancels duplicates. AND/OR/shift for bit-level tricks. O(1) space solutions.

• 136 · Single Number — Easy
• 191 · Number of 1 Bits — Easy
• 338 · Counting Bits — Easy
• 190 · Reverse Bits — Easy
• 268 · Missing Number — Easy
• 371 · Sum of Two Integers — Medium
• 7 · Reverse Integer — Medium