LeetCode Pattern Mastery

The Complete Guide to Recognising & Solving Every Pattern

26 Patterns · Code Templates · Recognition Keywords · Complexity Analysis

Covers: Two Pointers · Sliding Window · Binary Search · DP ·

Backtracking · Graphs · Heaps · Tries · and more

Use the Quick Reference table (next page) to identify patterns at a glance during an interview.
 Quick Reference — Pattern Selection Guide

When you see this signal in a problem → use this pattern.

Signal / Keyword in problem Pattern to use Complexity gain

Sorted array, pair/triplet sum Two Pointers O(N²) → O(N)

Linked list cycle / find middle Fast & Slow Pointers O(N) O(1) space

Longest/shortest contiguous subarray Sliding Window O(N²) → O(N)

Sorted search, find boundary Binary Search O(N) → O(log N)

Complement lookup, frequency count HashMap / HashSet O(N²) → O(N)

Overlapping subproblems, 1D Dynamic Programming 1D O(2^N) → O(N)

Two strings / grid optimization Dynamic Programming 2D O(2^N) → O(M×N)

All subsets, permutations, combinations Backtracking Smart pruning of O(N!)

Shortest path (unweighted) BFS O(V+E) guaranteed shortest

Connected components, flood fill DFS O(V+E) or O(M×N)

Tree path sums, BST validation Tree Traversal O(N) with correct ordering

K-largest/smallest, merge sorted Heap / Priority Queue O(N log K)

Make locally best choice Greedy O(N log N) with sort

Prefix matching, word dictionary Trie O(L) per operation

Overlapping ranges, scheduling Interval Problems O(N log N)

Bracket matching, nested structures Stack O(N²) → O(N)

Range sum queries, static array Prefix Sum O(N) per query → O(1)

Weighted shortest path Dijkstra O((V+E) log V)

Single number, missing number Bit Manipulation O(N) O(1) space

Primes, GCD, factorial, digits Math / Number Theory O(√N) to O(N log log N)

Tree Q queries, path between nodes LCA / Binary Lifting O(N×Q) → O((N+Q) log N)
Connected components, dynamic
DSU / Union-Find O(α(N)) per operation
edges

Prerequisites, task ordering Topological Sort O(N!) → O(V+E)

Point updates + range queries Segment / Fenwick Tree O(N) query → O(log N)

Next greater / smaller element Monotonic Stack O(N²) → O(N)

Minimize max / maximize min value Binary Search on Answer O(V×N) → O(N log V)
Section 1 — Arrays & Strings
Two Pointers
Category: Arrays & Strings | Difficulty: Easy → Medium

What it solves
Use two index pointers (usually left and right, or slow and fast) to scan through an array or string in a
single pass. Eliminates the need for a nested loop.

Naive vs Optimised
❌ Brute Force O(N²) ✅ Two Pointers O(N)

Check every pair with nested loops — TLE on Move pointers toward each other based on
large inputs conditions — single pass

How to recognise it
sorted array two sum remove duplicates

palindrome pair with target sum 3Sum

container with most water

Step-by-step approach
1 Sort the array if not already sorted (required for most two-pointer problems).

2 Place left pointer at index 0, right pointer at the last index.

3 While left < right: check condition. If too small → move left right. If too large → move right
left. If match → record answer.

4 Handle duplicates by skipping equal elements after a match to avoid duplicate results.

Complexity
Metric Value

Time O(N) after O(N log N) sort

Space O(1)
 Exam Tip: Two pointers almost always requires a SORTED array (or you sort first). If the array is
unsorted and sorting isn't allowed, use a HashMap instead.

Python implementation
# Two Sum II — sorted array
def two_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1]
elif s < target:
left += 1
else:
right -= 1
return []

# 3Sum — find all unique triplets summing to 0

def three_sum(nums):
[Link]()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip duplicates
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
[Link]([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -=
1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
Sliding Window
Category: Arrays & Strings | Difficulty: Medium

What it solves
Maintain a window of elements satisfying some condition. Expand by moving right pointer, shrink by
moving left pointer. Every element enters and exits the window at most once.

Naive vs Optimised
❌ Brute Force O(N²) ✅ Sliding Window O(N)

Single pass — each element processed at most

Check every subarray with nested loops
twice (enter + exit window)

How to recognise it
longest substring minimum window contiguous subarray

at most K distinct maximum sum subarray all positive values

Step-by-step approach
1 Initialise left = 0, right = 0, and a state variable (count, sum, hashmap, etc.).

2 Expand: add nums[right] to state, advance right pointer.

3 Shrink: while window is invalid, remove nums[left] from state, advance left pointer.

4 Update answer with current valid window. Every element enters/exits at most once → O(N).

Complexity
Metric Value

Time O(N)

Space O(K) where K = distinct elements

Exam Tip: Sliding window FAILS with negative numbers (shrinking doesn't always help). For
negatives, use Kadane's algorithm for max subarray or Prefix Sum + HashMap for target sum.
Python implementation
# Minimum window substring
def min_window(s, t):
need = {}
for c in t: need[c] = [Link](c, 0) + 1
have, required = 0, len(need)
window = {}
left = 0
result = ""
min_len = float('inf')

for right in range(len(s)):

c = s[right]
window[c] = [Link](c, 0) + 1
if c in need and window[c] == need[c]:
have += 1

while have == required: # valid window — try to shrink

if right - left + 1 < min_len:
min_len = right - left + 1
result = s[left:right+1]
window[s[left]] -= 1
if s[left] in need and window[s[left]] < need[s[left]]:
have -= 1
left += 1

return result
Binary Search (Classic + Variants)
Category: Arrays & Searching | Difficulty: Easy → Hard

What it solves
Eliminate half the search space each iteration by comparing with the midpoint. Works on any SORTED
array or any problem with a monotonic condition (true/false boundary).

Naive vs Optimised
❌ Linear Scan O(N) ✅ Binary Search O(log N)

Scan every element to find the target — Halve the search space each step — finds target
unnecessary when data is sorted in log N steps

How to recognise it
sorted array find target first/last position

rotated sorted array search insert position peak element

minimize maximum

Step-by-step approach
1 Set lo = 0, hi = len(array) - 1 (or the answer range for parametric search).

2 Compute mid = lo + (hi - lo) // 2 each iteration.

3 If array[mid] == target → found. If < target → lo = mid + 1. If > target → hi = mid - 1.

4 For 'find leftmost': when found, save mid and continue with hi = mid - 1. For 'find rightmost':
save mid and continue with lo = mid + 1.

Complexity
Metric Value

Classic search O(log N)

Space O(1)

Binary search on answer O(N log V)

 Exam Tip: Use lo + (hi - lo) // 2 instead of (lo + hi) // 2 to avoid integer overflow. For 'first true'
problems: when condition is met, don't stop — save the answer and continue searching left.

Python implementation
# Classic binary search
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target: return mid
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1

# Find leftmost position (first occurrence)

def search_left(nums, target):
lo, hi, result = 0, len(nums) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
result = mid
hi = mid - 1 # keep searching LEFT
elif nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return result

# Search in rotated sorted array

def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1
HashMap / HashSet
Category: Arrays & Strings | Difficulty: Easy → Medium

What it solves
Trade space for time — store elements in a hash structure for O(1) lookup. Eliminates nested loops for
'find complement', 'count occurrences', and 'check existence' problems.

Naive vs Optimised
❌ Nested Loops O(N²) ✅ HashMap O(N)

For each element, scan the rest of the array — Store elements in a map — O(1) lookup replaces
TLE the inner loop

How to recognise it
two sum anagram duplicate

frequency count first non-repeating group anagrams

subarray sum equals K

Step-by-step approach
1 Initialise an empty HashMap (or HashSet for existence-only checks).

2 For each element: check if the complement/answer exists in the map first.

3 If yes → found the answer. If no → store current element in the map.

4 For frequency problems: store {element: count} and iterate the map for the answer.

Complexity
Metric Value

Time O(N) average

Space O(N)

Lookup O(1) average

 Exam Tip: For 'subarray sum equals K': use a prefix sum HashMap. Store {prefix_sum: count}.
For each index, check if (current_prefix - K) exists in the map.

Python implementation
# Two Sum — unsorted array
def two_sum(nums, target):
seen = {} # value → index
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []

# Subarray sum equals K (handles negatives too)

def subarray_sum(nums, k):
prefix_count = {0: 1} # prefix_sum → frequency
prefix = 0
count = 0
for n in nums:
prefix += n
count += prefix_count.get(prefix - k, 0)
prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
return count

# Group anagrams
def group_anagrams(strs):
groups = {}
for s in strs:
key = tuple(sorted(s)) # sorted string as key
[Link](key, []).append(s)
return list([Link]())
Stack — Matching & Parsing
Category: Arrays & Strings | Difficulty: Easy → Medium

What it solves
Use a stack for problems requiring matching paired elements (brackets, tags) or parsing expressions.
The stack naturally handles LIFO order — the most recent unmatched element is always at the top.

Naive vs Optimised
❌ Counter only ✅ Stack O(N)

Counting opens/closes works for single bracket Push opens, pop and match closes — handles
types but fails for mixed types like ()[]{} any combination of paired elements

How to recognise it
valid parentheses decode string evaluate expression

daily temperatures asteroid collision remove k digits

basic calculator

Step-by-step approach
1 Initialise an empty stack.

2 For opening brackets/tags: push onto stack.

3 For closing brackets: check if stack is non-empty and top matches. If yes pop, if no →
invalid.

4 After processing all characters: stack should be empty for a valid string.

Complexity
Metric Value

Time O(N)

Space O(N)
 Exam Tip: Any time you need to 'remember' the most recent unresolved element and check it
against a future element, that's a stack problem. Brackets, nested structures, and expression
parsing are classic tells.

Python implementation
# Valid parentheses
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for c in s:
if c in mapping:
top = [Link]() if stack else '#'
if mapping[c] != top: return False
else:
[Link](c)
return not stack

# Decode string: "3[a2[bc]]" → "abcbcabcbcabcbc"

def decode_string(s):
stack = []
current_string = ""
current_num = 0
for c in s:
if [Link]():
current_num = current_num * 10 + int(c)
elif c == '[':
[Link]((current_string, current_num))
current_string, current_num = "", 0
elif c == ']':
prev_string, num = [Link]()
current_string = prev_string + num * current_string
else:
current_string += c
return current_string
Prefix Sum
Category: Arrays & Strings | Difficulty: Easy → Medium

What it solves
Precompute cumulative sums so any range sum [l, r] can be answered in O(1). The range sum equals
prefix[r+1] - prefix[l]. Extended with a HashMap for 'subarray sum equals K' problems.

Naive vs Optimised
❌ Recompute each range O(N) per query ✅ Prefix Sum O(1) per query

Sum from scratch for every query — O(N×Q) total O(N) precompute, then O(1) per range query

How to recognise it
range sum query subarray sum equals K pivot index

product except self running sum 2D prefix sum

binary subarrays with sum

Step-by-step approach
1 Build prefix array: prefix[0] = 0, prefix[i] = prefix[i-1] + nums[i-1].

2 Range sum [l, r] = prefix[r+1] - prefix[l] (0-indexed).

3 For 'count subarrays with sum K': maintain a running prefix sum and a HashMap {sum:
count}.

4 For each index: answer += map[prefix - K], then map[prefix] += 1.

Complexity
Metric Value

Precompute O(N)

Range query O(1)

Subarray sum count O(N)

 Exam Tip: For 'number of subarrays with sum = K': use prefix sum + HashMap. Ask: 'how many
times has (current_prefix - K) appeared before?' That count = number of valid subarrays ending
here.

Python implementation
# Static range sum queries
class NumArray:
def __init__(self, nums):
[Link] = [0] * (len(nums) + 1)
for i, n in enumerate(nums):
[Link][i+1] = [Link][i] + n

def sum_range(self, l, r):

return [Link][r+1] - [Link][l]

# Count subarrays with sum = k (handles negatives)

def subarray_sum(nums, k):
count = 0
prefix = 0
seen = {0: 1} # prefix_sum → frequency
for n in nums:
prefix += n
count += [Link](prefix - k, 0) # subarrays ending here with sum k
seen[prefix] = [Link](prefix, 0) + 1
return count

# Product of array except self (no division)

def product_except_self(nums):
n = len(nums)
result = [1] * n
left = 1
for i in range(n): # prefix products
result[i] = left
left *= nums[i]
right = 1
for i in range(n-1, -1, -1): # suffix products
result[i] *= right
right *= nums[i]
return result
Section 2 — Linked Lists
Fast & Slow Pointers (Floyd's)
Category: Linked Lists | Difficulty: Easy → Medium

What it solves
Two pointers moving at different speeds through a linked list or sequence. The fast pointer moves 2
steps, slow moves 1. They meet if a cycle exists.

Naive vs Optimised
❌ HashSet O(N) space ✅ Fast & Slow O(1) space

Track visited nodes in a set — works but uses Two pointers — cycle detection with no extra
O(N) extra space space

How to recognise it
linked list cycle find middle of list detect cycle

palindrome linked list happy number circular array

Step-by-step approach
1 Initialise slow = head, fast = head.

2 Move slow one step, fast two steps each iteration.

3 If fast or [Link] becomes null → no cycle. If slow == fast → cycle detected.

4 To find cycle start: reset slow to head. Move both one step until they meet — that's the
cycle entry point.

Complexity
Metric Value

Cycle detection O(N)

Find middle O(N)

Space O(1)
 Exam Tip: If fast and slow pointers meet → cycle exists. To find the START of the cycle: reset
slow to head, keep fast at meeting point, move both one step at a time — they meet at the cycle
start.

Python implementation
# Detect cycle in linked list
def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
return True
return False

# Find middle of linked list

def find_middle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
return slow # slow is at the middle

# Find cycle START node

def detect_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
slow = head # reset slow to head
while slow != fast: # move both at same speed
slow = [Link]
fast = [Link]
return slow # meeting point = cycle start
return None
Section 3 — Trees & Graphs
BFS (Breadth-First Search)
Category: Trees & Graphs | Difficulty: Easy → Medium

What it solves
Explore nodes level by level using a queue. Guarantees the SHORTEST path in an unweighted graph.
Visit all neighbours before going deeper.

Naive vs Optimised
❌ DFS for shortest path ✅ BFS O(V+E)

DFS finds A path, not necessarily the SHORTEST Queue-based level-order traversal — shortest
path in unweighted graphs path guaranteed

How to recognise it
shortest path minimum steps level order traversal

word ladder 01 matrix rotten oranges

number of islands

Step-by-step approach
1 Initialise queue with the start node(s). Mark start as visited immediately.

2 While queue is not empty: dequeue a node, process it.

3 For each unvisited neighbour: mark visited, enqueue with updated distance.

4 Return when target is found (guaranteed shortest) or when queue is empty (no path).

Complexity
Metric Value

Time O(V + E)

Space O(V) for queue

 Exam Tip: BFS = shortest path in unweighted graphs. Always use BFS (not DFS) when the
question asks for 'minimum steps', 'shortest path', or 'fewest operations'. Mark nodes visited
BEFORE enqueuing, not after dequeuing.

Python implementation
from collections import deque

# Shortest path in unweighted graph

def bfs(graph, start, target):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, dist = [Link]()
if node == target: return dist
for nei in graph[node]:
if nei not in visited:
[Link](nei) # mark BEFORE enqueue
[Link]((nei, dist + 1))
return -1

# Multi-source BFS (e.g. rotten oranges)

def multi_source_bfs(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2: [Link]((r, c, 0)) # all sources
elif grid[r][c] == 1: fresh += 1
minutes = 0
while queue:
r, c, t = [Link]()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
grid[nr][nc] = 2
fresh -= 1
minutes = max(minutes, t + 1)
[Link]((nr, nc, t + 1))
return minutes if fresh == 0 else -1
DFS — Graphs & Islands
Category: Trees & Graphs | Difficulty: Medium

What it solves
Explore as far as possible along each branch before backtracking. Ideal for connected component
counting, flood fill, cycle detection, and path existence problems.

Naive vs Optimised
❌ BFS for connected components ✅ DFS O(V+E)

BFS works but DFS is simpler and uses less code Recursive or iterative deep exploration — marks
for connectivity problems visited cells/nodes

How to recognise it
number of islands connected components flood fill

path exists surrounded regions clone graph

count provinces

Step-by-step approach
1 For each unvisited node/cell, call DFS and increment component count.

2 In DFS: mark current node as visited immediately (before recursing to avoid revisits).

3 Recurse into all valid unvisited neighbours.

4 Count = number of DFS calls from the outer loop = number of connected components.

Complexity
Metric Value

Time O(V + E) or O(M×N) for grids

Space O(V) call stack

 Exam Tip: For grid problems: treat each cell as a node, 4 directions as edges. Mark cells as
visited by overwriting the grid value (saves a visited set). Always check bounds before recursing.

Python implementation
# Number of islands — grid DFS
def num_islands(grid):
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: return
if grid[r][c] != '1': return
grid[r][c] = '#' # mark visited by overwriting
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':
dfs(r, c)
count += 1
return count

# Graph DFS — iterative to avoid recursion limit

def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = [Link]()
if node in visited: continue
[Link](node)
for nei in graph[node]:
if nei not in visited:
[Link](nei)
return visited
Tree Traversals & Patterns
Category: Trees & Graphs | Difficulty: Easy → Medium

What it solves
Navigate a binary tree in different orders. Inorder gives sorted output for BSTs. Preorder is used for
serialization. Postorder processes children before parents. Level-order processes row by row.

Naive vs Optimised
❌ Linear scan O(N²) ✅ Recursive/Iterative O(N)

For BST operations without using the BST Single pass through all nodes with correct order
property — misses the O(log N) advantage guarantees

How to recognise it
inorder traversal level order max depth

path sum lowest common ancestor validate BST

symmetric tree serialize tree

Step-by-step approach
1 Choose traversal order: inorder (left→root→right), preorder (root→left→right), postorder
(left→right→root), or level-order (BFS).

2 For recursive: define base case (node is None → return), then recursive case with the
pattern.

3 For path problems: pass accumulator down, return answer up.

4 For LCA: if both nodes are in different subtrees → current node is LCA.

Complexity
Metric Value

All traversals O(N)

BST search/insert O(log N) avg, O(N) worst

Space O(H) where H = height

Exam Tip: For BST problems: always use the BST property (left < root < right). Inorder traversal
of BST gives a sorted array. Validate BST by passing min/max bounds down the recursion.

Python implementation
# All traversals in one place
def inorder(root): # sorted output for BST
return inorder([Link]) + [[Link]] + inorder([Link]) if root else
[]

def preorder(root): # root first — good for serialization

return [[Link]] + preorder([Link]) + preorder([Link]) if root
else []

def postorder(root): # children first — good for deletion

return postorder([Link]) + postorder([Link]) + [[Link]] if root
else []

# Max path sum (passes through any node)

def max_path_sum(root):
result = [float('-inf')]
def dfs(node):
if not node: return 0
left = max(dfs([Link]), 0) # ignore negative paths
right = max(dfs([Link]), 0)
result[0] = max(result[0], left + [Link] + right) # update global
max
return [Link] + max(left, right) # return best single branch
dfs(root)
return result[0]

# Validate BST
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if [Link] <= lo or [Link] >= hi: return False
return (is_valid_bst([Link], lo, [Link]) and
is_valid_bst([Link], [Link], hi))
Dijkstra's Algorithm (Weighted Shortest Path)
Category: Trees & Graphs | Difficulty: Medium → Hard

What it solves
Find the shortest path in a weighted graph with NON-NEGATIVE edge weights. Uses a min-heap
(priority queue) to always process the closest unvisited node first.

Naive vs Optimised
❌ BFS for weighted graphs ✅ Dijkstra O((V+E) log V)

BFS assumes all edges have equal weight — Min-heap always processes nearest node —
wrong answer on weighted graphs correct shortest path on weighted graphs

How to recognise it
weighted shortest path network delay time cheapest flights

path with minimum cost non-negative weights single source shortest path

Step-by-step approach
1 Initialise dist[] = infinity for all nodes. dist[source] = 0. Push (0, source) to min-heap.

2 Pop (cost, node) from heap. If node already visited, skip.

3 Mark node as visited. For each neighbour: if dist[node] + edge_weight < dist[neighbour],
update dist and push to heap.

4 Return dist[] array or dist[target].

Complexity
Metric Value

Time O((V + E) log V)

Space O(V + E)

Exam Tip: Dijkstra FAILS on negative edge weights (use Bellman-Ford instead). Key insight:
 once a node is popped from the min-heap, its shortest distance is FINAL — skip it if visited.

Python implementation
import heapq

def dijkstra(graph, source, n):

# graph[u] = [(weight, v), ...]
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)] # (cost, node)
visited = set()

while heap:
cost, u = [Link](heap)
if u in visited: continue # already found shortest path
[Link](u)
for weight, v in graph[u]:
new_cost = cost + weight
if new_cost < dist[v]:
dist[v] = new_cost
[Link](heap, (new_cost, v))

return dist # dist[i] = shortest path from source to i

Trie (Prefix Tree)
Category: Trees & Graphs | Difficulty: Medium

What it solves
A tree where each node represents a character. Paths from root spell out strings. Enables O(L) prefix
search and autocomplete — far faster than searching through all strings.

Naive vs Optimised
❌ Linear scan O(N×L) ✅ Trie O(L)

Check every string for a prefix match — slow for Traverse the trie character by character — O(L)
large dictionaries per operation where L = word length

How to recognise it
word search II autocomplete prefix matching

implement trie longest common prefix add and search word

replace words

Step-by-step approach
1 Create TrieNode class with children dict (or array[26]) and is_end = False flag.

2 Insert: for each character, create a new node if it doesn't exist, then mark is_end = True at
the last character.

3 Search: traverse the trie character by character. If any character is missing → word not
found.

4 StartsWith (prefix): same as search but don't check is_end — just confirm all characters
exist.

Complexity
Metric Value

Insert / Search O(L) where L = word length

Space O(N × L) total for N words

 Exam Tip: Trie is the answer whenever you see: prefix matching, autocomplete, or word search
in a dictionary. Each TrieNode has children[26] and an is_end flag.

Python implementation
class TrieNode:
def __init__(self):
[Link] = {}
self.is_end = False

class Trie:
def __init__(self):
[Link] = TrieNode()

def insert(self, word):

node = [Link]
for c in word:
if c not in [Link]:
[Link][c] = TrieNode()
node = [Link][c]
node.is_end = True

def search(self, word):

node = [Link]
for c in word:
if c not in [Link]: return False
node = [Link][c]
return node.is_end # must end at a complete word

def starts_with(self, prefix):

node = [Link]
for c in prefix:
if c not in [Link]: return False
node = [Link][c]
return True # prefix exists regardless of is_end
Section 4 — Dynamic Programming
Dynamic Programming — 1D (Linear DP)
Category: Dynamic Programming | Difficulty: Medium → Hard

What it solves
Break the problem into overlapping subproblems. Store solutions to subproblems to avoid
recomputation. dp[i] represents the optimal answer for the first i elements.

Naive vs Optimised
❌ Recursion without memo O(2^N) ✅ Bottom-up DP O(N)

Recompute overlapping subproblems Fill dp[] left to right, each cell builds on previous
exponentially results

How to recognise it
maximum subarray climbing stairs coin change

house robber longest increasing subsequence minimum cost

fibonacci

Step-by-step approach
1 Define: what does dp[i] represent? (e.g. 'max profit using first i items').

2 Base case: what is dp[0] or dp[1]?

3 Transition: how does dp[i] depend on dp[i-1], dp[i-2], etc.? Write the recurrence.

4 Fill dp[] bottom-up from left to right. Return dp[n] or max(dp).

Complexity
Metric Value

Time O(N) to O(N²) depending on transitions

Space O(N) or O(1) with rolling variable

 Exam Tip: Ask: 'Does the answer for position i depend only on previous positions?' If yes → 1D
DP. The recurrence relation IS the solution — find it first, then code it.

Python implementation
# Climbing Stairs — dp[i] = ways to reach step i
def climb_stairs(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

# House Robber — dp[i] = max money robbing first i houses

def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) # skip or rob
return dp[-1]

# Longest Increasing Subsequence — O(N²)

def lis(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Dynamic Programming — 2D (Grid / String DP)
Category: Dynamic Programming | Difficulty: Medium → Hard

What it solves
Use a 2D table where dp[i][j] represents the answer for a subproblem involving the first i elements of
one input and first j elements of another (or a grid position).

Naive vs Optimised
❌ Recursion O(2^(M+N)) ✅ 2D DP O(M×N)

Fill table row by row — each cell references

Exponential recomputation without memoization
previous rows/columns

How to recognise it
longest common subsequence edit distance unique paths

minimum path sum interleaving strings regex matching

knapsack

Step-by-step approach
1 Define: what does dp[i][j] represent? Be precise.

2 Base cases: fill dp[0][j] and dp[i][0] (empty string / start of grid).

3 Transition: when characters match vs don't match (string DP), or when moving from
adjacent cells (grid DP).

4 Fill row by row, return dp[m][n].

Complexity
Metric Value

Time O(M × N)

Space O(M × N) or O(N) with rolling row

 Exam Tip: For string DP: dp[i][j] usually represents the answer for s1[:i] and s2[:j]. Always draw
the table for small examples to see the pattern before coding.

Python implementation
# Longest Common Subsequence
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # characters match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]

# Edit Distance (Levenshtein)

def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i # delete all
for j in range(n + 1): dp[0][j] = j # insert all
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
return dp[m][n]
Section 5 — Recursion & Search
Backtracking
Category: Recursion & Search | Difficulty: Medium → Hard

What it solves
Build solutions incrementally and abandon (backtrack) as soon as a partial solution cannot lead to a
valid complete solution. Explores the solution space like a pruned decision tree.

Naive vs Optimised
❌ Generate All O(N!) ✅ Backtracking O(pruned tree)

Generate every permutation/combination and Prune invalid branches early — dramatically

filter — wastes work on invalid branches reduces actual work

How to recognise it
all permutations all subsets all combinations

N-Queens word search sudoku solver

generate parentheses

Step-by-step approach
1 Define the recursive function with: current path, starting index (for combinations), and result
list.

2 Base case: if path satisfies the condition, add a copy of path to result and return.

3 Loop through valid choices. Add choice to path, recurse, then remove choice (backtrack).

4 Add pruning conditions to skip invalid choices early (e.g. skip duplicates, stop if sum
exceeds target).

Complexity
Metric Value

Subsets O(N × 2^N)

Permutations O(N × N!)

Combinations O(N × C(N,K))

Exam Tip: Backtracking template is always the same: (1) base case → add to result, (2) loop
through choices, (3) make choice, (4) recurse, (5) undo choice. The pruning condition is where
the problem-specific logic lives.

Python implementation
# All subsets
def subsets(nums):
result = []
def backtrack(start, path):
[Link](path[:]) # add copy at every node
for i in range(start, len(nums)):
[Link](nums[i])
backtrack(i + 1, path)
[Link]() # undo choice
backtrack(0, [])
return result

# Combination sum (with repetition)

def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
[Link](path[:]); return
if remaining < 0: return # prune: exceeded target
for i in range(start, len(candidates)):
[Link](candidates[i])
backtrack(i, path, remaining - candidates[i])
[Link]()
backtrack(0, [], target)
return result

# All permutations
def permutations(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
[Link](path[:]); return
for i in range(len(nums)):
if used[i]: continue
used[i] = True
[Link](nums[i])
backtrack(path, used)
[Link]()
used[i] = False
backtrack([], [False] * len(nums))
return result
Section 6 — Sorting & Ordering
Heap / Priority Queue
Category: Sorting & Ordering | Difficulty: Medium

What it solves
Maintain a dynamic sorted structure where you can always extract the min or max in O(log N).
Essential for K-largest/smallest problems and merge-sorted-lists problems.

Naive vs Optimised
❌ Sort then slice O(N log N) ✅ Heap O(N log K)

Sort entire array to find K-th element — overkill Maintain a K-size heap — only keep track of the
when K << N best K elements

How to recognise it
K largest K smallest K-th largest

merge K sorted lists top K frequent find median data stream

task scheduler

Step-by-step approach
1 For K-largest: initialise a min-heap of size K with the first K elements.

2 For each remaining element: if it's larger than heap[0] (the minimum), pop and push the
new element.

3 After processing all elements, the heap contains the K largest.

4 For K-th largest specifically: return heap[0] (the smallest of the K largest = K-th largest
overall).

Complexity
Metric Value

K-th largest O(N log K)

Heap push/pop O(log N)

Peek min/max O(1)

Exam Tip: Python's heapq is a MIN-heap. For max-heap: negate all values. For K largest
elements: use a MIN-heap of size K — if new element > heap top, pop and push. The heap
always holds the K largest seen so far.

Python implementation
import heapq

# K largest elements
def k_largest(nums, k):
min_heap = nums[:k]
[Link](min_heap) # O(K)
for n in nums[k:]:
if n > min_heap[0]:
[Link](min_heap, n) # pop min, push n
return min_heap # contains K largest

# K-th largest
def kth_largest(nums, k):
return [Link](k, nums)[-1]
# or maintain heap of size k as above and return heap[0]

# Merge K sorted lists

def merge_k_sorted(lists):
heap = []
for i, lst in enumerate(lists):
if lst: [Link](heap, (lst[0], i, 0))
result = []
while heap:
val, i, j = [Link](heap)
[Link](val)
if j + 1 < len(lists[i]):
[Link](heap, (lists[i][j+1], i, j+1))
return result

# Find median from data stream

class MedianFinder:
def __init__(self):
[Link] = [] # max-heap (negate values)
[Link] = [] # min-heap
def add_num(self, num):
[Link]([Link], -num)
[Link]([Link], -[Link]([Link]))
if len([Link]) > len([Link]):
[Link]([Link], -[Link]([Link]))
def find_median(self):
if len([Link]) > len([Link]): return -[Link][0]
return (-[Link][0] + [Link][0]) / 2
Interval Problems
Category: Sorting & Ordering | Difficulty: Medium

What it solves
Problems involving ranges [start, end]. The key technique is sorting by start time, then using greedy
merging or a min-heap to handle overlaps.

Naive vs Optimised
❌ Nested loop O(N²) ✅ Sort + sweep O(N log N)

Sort by start, then one pass to

Check every pair of intervals for overlap — TLE
merge/count/schedule

How to recognise it
meeting rooms merge intervals insert interval

non-overlapping intervals minimum meeting rooms employee free time

Step-by-step approach
1 Sort intervals by start time (or end time depending on the problem).

2 For merging: iterate and check if current interval overlaps with the last merged one. If yes,
extend. If no, append.

3 For minimum rooms: use a min-heap. Push end times. For each new interval, if it starts
after heap top, pop (room freed). Always push current end time.

4 Return merged list or heap size (= rooms in use).

Complexity
Metric Value

Sort O(N log N)

Sweep O(N log N) with heap, O(N) merge-only

 Exam Tip: Sort intervals by START time for merging. Sort by END time for scheduling (greedy:
always pick the meeting that ends earliest). For 'minimum rooms', use a min-heap of end times.

Python implementation
# Minimum meeting rooms needed
import heapq
def min_meeting_rooms(intervals):
[Link](key=lambda x: x[0])
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
[Link](heap, end) # reuse room
else:
[Link](heap, end) # need new room
return len(heap)

# Insert interval into sorted list

def insert(intervals, new_interval):
result = []
i, n = 0, len(intervals)
# Add all intervals that end before new one starts
while i < n and intervals[i][1] < new_interval[0]:
[Link](intervals[i]); i += 1
# Merge all overlapping intervals
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
[Link](new_interval)
[Link](intervals[i:])
return result
Greedy Algorithms
Category: Optimization | Difficulty: Medium

What it solves
Make the locally optimal choice at each step with the hope that it leads to the globally optimal solution.
Greedy works when the problem has the 'greedy choice property' — local optimum leads to global
optimum.

Naive vs Optimised
❌ DP for all optimization ✅ Greedy O(N) or O(N log N)

DP is correct but often O(N²) — greedy gives One pass making locally optimal choices — no
O(N) when the greedy property holds backtracking needed

How to recognise it
jump game gas station meeting rooms

interval scheduling minimum coins assign cookies

task scheduler

Step-by-step approach
1 Sort if the order of processing matters (e.g. sort intervals by start or end time).

2 Initialise tracking variables (current reach, current sum, count, etc.).

3 Iterate and make the greedy choice at each step — always pick the locally best option.

4 Return the accumulated result. No backtracking needed.

Complexity
Metric Value

Time O(N) or O(N log N) with sort

Space O(1)
 Exam Tip: Greedy works when: (1) making the best local choice never hurts you globally, AND
(2) the problem has optimal substructure. If in doubt between greedy and DP — check with a
small example. If greedy gives wrong answer → use DP.

Python implementation
# Jump Game II — minimum jumps to reach end
def jump(nums):
jumps = 0
current_end = 0 # farthest we can reach with current jumps
farthest = 0 # farthest we can reach at all
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end: # must take a jump
jumps += 1
current_end = farthest
return jumps

# Merge intervals
def merge_intervals(intervals):
[Link](key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap
merged[-1][1] = max(merged[-1][1], end)
else:
[Link]([start, end])
return merged

# Gas station — circular route

def can_complete_circuit(gas, cost):
total, tank, start = 0, 0, 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0: # can't reach from current start
start = i + 1
tank = 0
return start if total >= 0 else -1
Section 7 — Math & Bits
Bit Manipulation
Category: Math & Bits | Difficulty: Easy → Medium

What it solves
Use bitwise operations (&, |, ^, ~, <<, >>) to solve problems in O(1) or O(N) with constant space. XOR
is especially powerful for finding single/missing numbers.

Naive vs Optimised
❌ Sort or HashMap ✅ Bit ops O(N) O(1) space

Using extra space or sorting when bitwise ops XOR, AND, shifts — no extra data structures
can solve it in O(1) space needed

How to recognise it
single number missing number count bits

power of two reverse bits XOR queries

sum of two integers without +

Step-by-step approach
1 Identify the bit operation: XOR for finding single/missing, AND for masking, shifts for powers
of 2.

2 For 'single number': XOR all elements — duplicates cancel out (x^x=0), leaving the unique
element.

3 For 'count set bits': use Brian Kernighan's trick: while n > 0: count += 1; n = n & (n-1).

4 For 'power of 2': n > 0 and (n & (n-1)) == 0 — a power of 2 has exactly one set bit.

Complexity
Metric Value

Single number XOR O(N) time, O(1) space

Count bits O(1) per number

Most bit ops O(1)

Exam Tip: XOR tricks: x ^ x = 0, x ^ 0 = x. XOR all elements to find the one that appears odd
times. n & (n-1) removes the lowest set bit — use it to count set bits.

Python implementation
# Single number (appears once, all others twice)
def single_number(nums):
result = 0
for n in nums: result ^= n # x^x=0, x^0=x
return result

# Missing number 0..n

def missing_number(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)
# OR: XOR 0..n with all elements — missing cancels out

# Count set bits (Brian Kernighan)

def count_bits(n):
count = 0
while n:
n &= n - 1 # removes lowest set bit
count += 1
return count

# Add two integers without + operator

def get_sum(a, b):
mask = 0xFFFFFFFF
while b & mask:
carry = (a & b) << 1
a = a ^ b
b = carry
return a if b == 0 else a & mask
Math & Number Theory Patterns
Category: Math & Bits | Difficulty: Easy → Medium

What it solves
Problems solvable with mathematical insights: modular arithmetic, GCD, prime sieve, digit
manipulation. Recognizing the math avoids unnecessary data structures.

Naive vs Optimised
❌ Brute force simulation ✅ Math formula O(1) or O(√N)

Iterate through all numbers or combinations —

Direct computation using mathematical properties
TLE on large ranges

How to recognise it
power of N factorial trailing zeros palindrome number

roman numerals excel column count primes

greatest common divisor

Step-by-step approach
1 Identify if a mathematical property directly solves the problem (trailing zeros = count 5s,
GCD = Euclidean).

2 For number digit problems: extract digits with n % 10 and n // 10.

3 For prime sieve: start with all True, mark multiples of each prime as False from p² upward.

4 For modular arithmetic: use (a * b) % mod to prevent overflow.

Complexity
Metric Value

GCD O(log min(a,b))

Prime sieve O(N log log N)

Digit extraction O(log N)

 Exam Tip: For counting primes up to N: use the Sieve of Eratosthenes O(N log log N). For GCD:
use Euclidean algorithm — gcd(a, b) = gcd(b, a%b). For factorial trailing zeros: count factors of 5.

Python implementation
# GCD — Euclidean algorithm
def gcd(a, b):
while b: a, b = b, a % b
return a

# Sieve of Eratosthenes — count primes up to n

def count_primes(n):
if n < 2: return 0
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n, i): # start from i²
is_prime[j] = False
return sum(is_prime)

# Factorial trailing zeros = count of 5s

def trailing_zeros(n):
count = 0
while n >= 5:
n //= 5
count += n
return count

# Fast power modulo — square and multiply

def power_mod(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1: result = result * base % mod
base = base * base % mod
exp //= 2
return result
 Final Cheat Sheet — The Meta-Rules

Rule 1: Read constraints FIRST, not the problem

Constraints tell you the expected complexity. N ≤ 20 → exponential OK. N ≤ 10^3 → O(N²) OK. N ≤
10^6 → must be O(N) or O(N log N).

N constraint Max complexity Patterns to consider

N ≤ 20 O(2^N) or O(N!) Backtracking, bitmask DP

N ≤ 10^2 O(N³) 3-nested loops, Floyd-Warshall

N ≤ 10^3 O(N²) 2D DP, nested loops, bubble sort

N ≤ 10^5 O(N log N) Sort + scan, heap, binary search, segment tree

N ≤ 10^6 O(N) Sliding window, two pointers, prefix sum, hash

N ≤ 10^9 O(log N) or O(√N) Binary search, math, sieve

Rule 2: Keyword → Pattern mapping

Train yourself to trigger a pattern from a single keyword. These are the most reliable tells:

Keyword Pattern Why

Window expands/shrinks in
"Contiguous subarray" Sliding Window
O(N)

Sorted enables pointer

"Sorted + pair/triplet" Two Pointers
movement

O(N log K) beats O(N log N)

"K-th largest" Heap of size K
sort

"All combinations" Backtracking Decision tree with pruning

BFS (unweighted) / Dijkstra

"Shortest path" Queue = level order = shortest
(weighted)

"Connected components" DFS or DSU Both O(N) — DSU for dynamic

"Prefix matching" Trie O(L) per lookup vs O(N×L) scan

"Minimum/maximum of
DP or Greedy Try greedy first — simpler
something"
"Minimize the maximum" Binary Search on Answer Parametric search on the value

"Prerequisites" Topological Sort DAG ordering = topo sort

Rule 3: DP vs Greedy decision

Use GREEDY when... Use DP when...

Local optimum always leads to global optimum Local optimum may NOT lead to global optimum
Example: always pick the meeting that ends Example: coin change — greedy fails for some
earliest denominations

LeetCode Pattern Mastery · 26 Patterns · Comprehensive DSA Interview Guide