TL;DR
- Pattern recognition beats brute-force grinding for FAANG coding interviews.
- Ten patterns cover the vast majority of questions: sliding window, two pointers, BFS, DFS, modified binary search, dynamic programming, backtracking, topological sort, trie, and union find, with monotonic stack as a frequent bonus.
- Spend two to three days per pattern, solve three to five problems each before moving on, then mix patterns to simulate real interview pressure.
- Each pattern in this guide includes Python code and a key insight.
Introduction
If you have been grinding LeetCode problems randomly, you are not alone. Most candidates spend weeks solving hundreds of problems without a clear strategy, only to freeze when they encounter a new variation in an actual interview. The secret that separates successful candidates from the rest is pattern recognition. Once you internalize the core patterns behind coding problems, you can break down almost any question you face.
This guide covers the 10 most frequently tested patterns in coding interviews at companies like Google, Meta, Amazon, Apple, and Microsoft. Each pattern includes an explanation of when to use it, the key idea behind it, and a working Python example.
Table of Contents
- Sliding Window
- Two Pointers
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
- Modified Binary Search
- Dynamic Programming
- Backtracking
- Topological Sort
- Trie (Prefix Tree)
- Union Find (Disjoint Set)
- Bonus: Monotonic Stack
- How to Practice These Patterns Effectively
1. Sliding Window
The sliding window pattern is used when you need to examine a contiguous subset of elements in an array or string. Instead of recalculating everything from scratch for each subset, you slide the window forward and update incrementally. This reduces brute-force O(n^2) solutions down to O(n).
When to use it:
- Problems asking for the longest or shortest substring or subarray with a given condition
- Problems involving contiguous sequences with a constraint (sum, distinct count, etc.)
- Keywords like "contiguous," "substring," "subarray," or "window"
Classic problems: Longest Substring Without Repeating Characters, Minimum Window Substring, Maximum Sum Subarray of Size K
def length_of_longest_substring(s: str) -> int:
"""
LeetCode 3: Longest Substring Without Repeating Characters
Sliding window with a set to track characters in current window.
Time: O(n) | Space: O(min(n, 26))
"""
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_lengthKey insight: Maintain two pointers (left and right) defining the window. Expand right to explore, shrink left to satisfy constraints. The window never moves backward, giving you linear time.
2. Two Pointers
Two pointers is one of the simplest yet most powerful techniques. You place one pointer at each end of a sorted array (or at strategic positions) and move them toward each other based on a condition. It is also used with linked lists where a slow and fast pointer can detect cycles or find midpoints.
When to use it:
- Sorted array problems asking for pairs that satisfy a condition
- Problems involving partitioning or rearranging elements in place
- Linked list cycle detection or finding the middle node
- Removing duplicates from a sorted array
Classic problems: Two Sum II (sorted input), 3Sum, Container With Most Water, Linked List Cycle
def three_sum(nums: list[int]) -> list[list[int]]:
"""
LeetCode 15: 3Sum
Sort + two pointers to find all unique triplets summing to zero.
Time: O(n^2) | Space: O(1) excluding output
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicates for first element
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # skip duplicates
while left < right and nums[right] == nums[right - 1]:
right -= 1 # skip duplicates
left += 1
right -= 1
return resultKey insight: Sorting the array first unlocks the ability to make intelligent decisions about which pointer to move. If the sum is too small, move the left pointer right. If too large, move the right pointer left.
3. BFS (Breadth-First Search)
BFS explores nodes level by level using a queue. It is the go-to algorithm whenever you need the shortest path in an unweighted graph or need to process nodes in order of their distance from a starting point.
When to use it:
- Shortest path in an unweighted graph or grid
- Level-order traversal of a tree
- Problems involving "minimum number of steps" or "fewest operations"
- Anything that requires exploring neighbors before going deeper
Classic problems: Binary Tree Level Order Traversal, Rotting Oranges, Word Ladder, Shortest Path in Binary Matrix
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
"""
LeetCode 994: Rotting Oranges
Multi-source BFS starting from all rotten oranges simultaneously.
Time: O(m * n) | Space: O(m * n)
"""
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh_count = 0
# Initialize: find all rotten oranges and count fresh ones
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # row, col, minutes
elif grid[r][c] == 1:
fresh_count += 1
if fresh_count == 0:
return 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
max_minutes = 0
while queue:
r, c, minutes = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh_count -= 1
max_minutes = max(max_minutes, minutes + 1)
queue.append((nr, nc, minutes + 1))
return max_minutes if fresh_count == 0 else -1Key insight: BFS guarantees that the first time you reach a node, you have found the shortest path to it. Multi-source BFS (starting from multiple points simultaneously) is a common pattern in grid problems.
4. DFS (Depth-First Search)
DFS dives as deep as possible along one path before backtracking. It is implemented with recursion or an explicit stack and works naturally for problems involving tree or graph traversal, connected components, and pathfinding where you need to explore all possibilities.
When to use it:
- Tree traversal (inorder, preorder, postorder)
- Counting connected components or islands in a grid
- Detecting cycles in a graph
- Path-finding problems where you need all paths, not just the shortest
Classic problems: Number of Islands, Path Sum, Clone Graph, Course Schedule (cycle detection)
def num_islands(grid: list[list[str]]) -> int:
"""
LeetCode 200: Number of Islands
DFS to mark visited land cells and count connected components.
Time: O(m * n) | Space: O(m * n) for recursion stack
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # mark as visited
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return countKey insight: DFS is ideal for exploring entire connected regions. In grid problems, you can often modify the grid in place to mark visited cells, avoiding the need for a separate visited set.
5. Modified Binary Search
Standard binary search finds a target in a sorted array. Modified binary search extends this to handle rotated arrays, finding boundaries, searching in 2D matrices, or minimizing/maximizing a value over a search space. The key is recognizing that you can binary search whenever a monotonic condition exists.
When to use it:
- Searching in a sorted or rotated sorted array
- Finding the first or last occurrence of a value
- Minimizing the maximum or maximizing the minimum (binary search on the answer)
- Problems where the search space can be halved at each step
Classic problems: Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Median of Two Sorted Arrays
def search_rotated(nums: list[int], target: int) -> int:
"""
LeetCode 33: Search in Rotated Sorted Array
Modified binary search that determines which half is sorted.
Time: O(log n) | Space: O(1)
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Key insight: In a rotated sorted array, at least one half is always properly sorted. Determine which half is sorted and check if the target lies within that range to decide which half to discard.
6. Dynamic Programming
Dynamic programming (DP) breaks a complex problem into overlapping subproblems and stores solutions to avoid redundant computation. The two approaches are top-down (memoization) and bottom-up (tabulation). DP problems are among the most feared in interviews, but they follow learnable patterns.
When to use it:
- Optimization problems asking for minimum cost, maximum profit, or number of ways
- Problems with overlapping subproblems and optimal substructure
- Sequence problems (longest increasing subsequence, edit distance)
- Grid path problems (unique paths, minimum path sum)
Classic problems: Climbing Stairs, Coin Change, Longest Common Subsequence, House Robber, 0/1 Knapsack
def coin_change(coins: list[int], amount: int) -> int:
"""
LeetCode 322: Coin Change
Bottom-up DP. dp[i] = minimum coins needed to make amount i.
Time: O(amount * len(coins)) | Space: O(amount)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins needed for amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
return dp[amount] if dp[amount] != float('inf') else -1Key insight: Start by defining the state clearly: what does dp[i] represent? Then find the recurrence relation that connects dp[i] to smaller subproblems. Most DP problems fall into a few categories: linear, grid-based, interval, or knapsack-type. Once those four feel familiar, move on to the top 20 dynamic programming patterns, which also cover string, tree, bitmask, and stock trading DP.
7. Backtracking
Backtracking is a refined brute-force approach. You build a solution incrementally and abandon a path as soon as you determine it cannot lead to a valid solution. It is essentially DFS with pruning.
When to use it:
- Generating all permutations or combinations
- Solving constraint satisfaction problems (N-Queens, Sudoku)
- Finding all paths or subsets that satisfy certain conditions
- Problems where you need to explore a decision tree
Classic problems: Subsets, Permutations, Combination Sum, N-Queens, Word Search
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
"""
LeetCode 39: Combination Sum
Backtracking with reuse of elements allowed.
Time: O(n^(target/min)) | Space: O(target/min) for recursion
"""
result = []
def backtrack(start, current_combo, remaining):
if remaining == 0:
result.append(current_combo[:]) # found valid combination
return
if remaining < 0:
return # prune: exceeded target
for i in range(start, len(candidates)):
current_combo.append(candidates[i])
backtrack(i, current_combo, remaining - candidates[i])
current_combo.pop() # undo choice (backtrack)
backtrack(0, [], target)
return resultKey insight: The template is always the same: choose, explore, unchoose. The start parameter prevents generating duplicate combinations. Pruning (returning early when the remaining sum goes negative) dramatically improves performance.
8. Topological Sort
Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u to v, u comes before v. It is the foundation for dependency resolution problems.
When to use it:
- Course scheduling or task ordering with prerequisites
- Build system dependency resolution
- Detecting cycles in directed graphs
- Any problem involving ordering with dependencies
Classic problems: Course Schedule, Course Schedule II, Alien Dictionary, Parallel Courses
from collections import deque, defaultdict
def find_order(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
"""
LeetCode 210: Course Schedule II
Kahn's algorithm (BFS-based topological sort).
Time: O(V + E) | Space: O(V + E)
"""
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
# Start with courses that have no prerequisites
queue = deque()
for i in range(num_courses):
if in_degree[i] == 0:
queue.append(i)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If we processed all courses, no cycle exists
return order if len(order) == num_courses else []Key insight: Kahn's algorithm uses in-degree counting. Start with all nodes that have zero in-degree (no dependencies), process them, reduce in-degrees of their neighbors, and repeat. If the final ordering contains fewer nodes than the total, a cycle exists. The graph algorithms interview guide shows the DFS-based alternative in Python, alongside BFS, shortest paths, and union find.
9. Trie (Prefix Tree)
A trie is a tree-like data structure that stores strings character by character. Each node represents a single character, and paths from the root to marked nodes represent complete words. Tries enable extremely fast prefix lookups.
When to use it:
- Autocomplete or prefix-based search
- Spell checking and word validation
- Problems involving common prefixes among strings
- Word search in a 2D grid with a dictionary
Classic problems: Implement Trie, Word Search II, Design Add and Search Words Data Structure, Longest Word in Dictionary
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
"""
LeetCode 208: Implement Trie (Prefix Tree)
Time: O(m) per operation where m is word length
Space: O(total characters across all words)
"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self._find_node(word)
return node is not None and node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
return self._find_node(prefix) is not None
def _find_node(self, prefix: str):
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return nodeKey insight: A trie trades space for speed. It gives you O(m) lookup for any prefix query where m is the prefix length, regardless of how many words are stored. When combined with DFS (like in Word Search II), it allows early termination of invalid paths.
10. Union Find (Disjoint Set)
Union Find is a data structure that tracks elements partitioned into disjoint sets. It supports two operations efficiently: find (determine which set an element belongs to) and union (merge two sets). With path compression and union by rank, both operations run in nearly O(1) amortized time.
When to use it:
- Grouping connected elements (connected components)
- Detecting cycles in undirected graphs
- Problems involving merging groups dynamically
- Redundant connection detection
Classic problems: Number of Connected Components, Redundant Connection, Accounts Merge, Longest Consecutive Sequence
class UnionFind:
"""
Union Find with path compression and union by rank.
Time: O(alpha(n)) per operation (nearly O(1))
Space: O(n)
"""
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False # already in same set
# Union by rank
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
self.components -= 1
return True
def count_components(n: int, edges: list[list[int]]) -> int:
"""
LeetCode 323: Number of Connected Components in an Undirected Graph
"""
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.componentsKey insight: Union Find shines when you need to dynamically group elements and quickly check if two elements are already connected. Path compression flattens the tree structure over time, making future queries faster.
Bonus: Monotonic Stack
A monotonic stack maintains elements in either strictly increasing or decreasing order. It is invaluable for problems involving "next greater element" or "previous smaller element" queries.
When to use it:
- Finding the next greater or smaller element for each position
- Histogram and area problems
- Stock span and temperature problems
- Problems where you need to look both forward and backward efficiently
Classic problems: Daily Temperatures, Largest Rectangle in Histogram, Next Greater Element, Trapping Rain Water
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""
LeetCode 739: Daily Temperatures
Monotonic decreasing stack storing indices.
Time: O(n) | Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # stores indices of temperatures waiting for a warmer day
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return resultKey insight: Each element is pushed and popped from the stack at most once, giving O(n) total time. The stack stores indices rather than values, which lets you calculate distances between elements.
How to Practice These Patterns Effectively
Knowing the patterns is only half the battle. Here is a structured approach to mastering them:
Step 1: Learn one pattern at a time
Do not try to tackle all patterns simultaneously. Spend 2-3 days on each pattern, solving 3-5 problems of increasing difficulty within that pattern before moving on.
Step 2: Solve without looking at solutions first
Give yourself 30-45 minutes per problem. If you are stuck, review the pattern explanation rather than jumping to the editorial. Building the muscle memory of struggling through a problem is what makes patterns stick.
Step 3: Review and categorize
After solving a problem, tag it with the pattern you used. Over time, you will start recognizing patterns within the first few seconds of reading a new problem.
Step 4: Mix it up
Once you have covered all 10 patterns, do random practice sessions where you pull problems from different patterns. This simulates real interview conditions where you do not know in advance which pattern applies.
Step 5: Use the right tools
Tools like PhantomCodeAI can accelerate your learning by providing real-time guidance as you work through LeetCode problems. When you are stuck on a pattern, getting a hint about the approach (without seeing the full solution) is far more valuable than reading the editorial.
Mastering these 10 patterns will cover the vast majority of coding interview questions at any company. The goal is not to memorize solutions but to develop the intuition that lets you map any new problem to a pattern you already know. Start with the patterns you find easiest, build momentum, and work your way through the harder ones. With focused practice, you will walk into your next interview ready to tackle whatever they throw at you.
Frequently asked questions
Which LeetCode patterns are most important for FAANG coding interviews?Sliding window, two pointers, BFS, DFS, modified binary search, dynamic programming, backtracking, topological sort, trie, and union find cover the majority of FAANG questions. Monotonic stack is a frequent bonus for next-greater-element problems. Mastering these ten patterns is more valuable than solving 500 random problems.
When should I use sliding window versus two pointers?Sliding window is for contiguous subarray or substring problems with a constraint like 'longest substring without repeating' or 'maximum sum size k'. Two pointers is for sorted arrays, palindrome checks, partitioning in place, or linked list cycle detection. Sliding window maintains a running statistic between left and right; two pointers usually moves toward each other based on a comparison.
How do I recognize a dynamic programming problem in an interview?Look for optimization questions asking for minimum cost, maximum profit, or number of ways, plus signs of overlapping subproblems and optimal substructure. Sequence problems like longest increasing subsequence and edit distance, and grid path problems like unique paths and minimum path sum, are almost always DP. Define dp[i] precisely, then find the recurrence to smaller subproblems.
What is the difference between Kahn's algorithm and DFS for topological sort?Kahn's algorithm is BFS-based: start with nodes that have zero in-degree, process them, decrement in-degrees of their neighbors, and repeat. DFS-based topological sort recurses into descendants and pushes nodes onto a stack on the way out. Both are O(V+E). Kahn's makes cycle detection trivial: if the final ordering has fewer nodes than the graph, a cycle exists.
How long should I spend on each LeetCode pattern before moving on?Two to three days per pattern, solving three to five problems of increasing difficulty within that pattern. Build muscle memory by struggling through problems for 30 to 45 minutes before checking the editorial. Once you have covered all ten patterns, do random mixed sessions to simulate real interview conditions where you do not know which pattern applies. A timed mock coding interview adds a 45-minute clock and grades how quickly you spot the underlying pattern.