INTERVIEW PREP — CODING PATTERNS

DSA PATTERNS MASTER GUIDE

19 Essential Patterns • P1 Must Master + P2 High Priority
Each pattern: Core idea • Template code • Classic problems • Complexity • Pitfalls
 PATTERN OVERVIEW — ALL 19 TECHNIQUES

# Pattern Priority Why It Matters Rank

1 Two Pointers P1 MUST MASTER Eliminates nested loops; O(n²)→O(n) 1
2 Sliding Window P1 MUST MASTER Substring/subarray optimization; reuses 1
computation
3 Binary Search P1 MUST MASTER Reduces search space from O(n) to O(log 1
n)
4 DFS + Backtracking P1 MUST MASTER All-paths exploration with pruning 1
5 BFS P1 MUST MASTER Shortest path in unweighted graphs 1
6 Dynamic Programming P1 MUST MASTER Overlapping subproblems → polynomial 1
7 Hashing P1 MUST MASTER O(n²)→O(n) via space-time tradeoff 1
8 Heap / Priority Queue P1 MUST MASTER Top-K & scheduling in O(n log k) 1
9 Union-Find P1 MUST MASTER Connectivity with near O(1) ops 2
1 Monotonic Stack P1 MUST MASTER O(n²)→O(n) for comparison problems 2
0
1 Trie (Prefix Tree) P2 HIGH PRIORITY O(word length) string lookups 2
1
1 Greedy P1 MUST MASTER Local optimal → global optimal 2
2
1 Backtracking P2 HIGH PRIORITY Exhaustive search with pruning 2
3
1 Topological Sort P2 HIGH PRIORITY Dependency resolution in DAGs 3
4
1 Sorting P2 HIGH PRIORITY Preprocessing for greedy/binary search 3
5
1 Prefix Sum P2 HIGH PRIORITY O(n²)→O(1) range queries 3
6
1 Divide and Conquer P2 HIGH PRIORITY Recursive subproblem decomposition 3
7
1 Merge Intervals P2 HIGH PRIORITY Greedy interval management in O(n log n) 3
8
1 Tree Traversal P2 HIGH PRIORITY Foundation of all tree problems 3
9
 P1 — MUST MASTER PATTERNS

1 Two Pointers P1 — MUST MASTER ★ Rank 1

Use two index variables that move through a data structure — usually from both ends toward the middle, or both
moving in the same direction at different speeds (fast/slow). Eliminates the need for a nested loop.

When to Use
• Sorted array + find pair/triplet with target sum
• Remove duplicates / filter in-place
• Palindrome check
• Container with most water / trapping rain water
• Cycle detection in linked list (Floyd's tortoise & hare)

Opposite-Direction Template
Python
def two_pointer_opposite(arr, target):
left, right = 0, len(arr) - 1
while left < right:
curr = arr[left] + arr[right]
if curr == target:
return [left, right] # found
elif curr < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []

# Requires SORTED array — sort first if unsorted: O(n log n + n) = O(n log n)

Fast / Slow Pointer — Cycle Detection

Python
def has_cycle(head): # Floyd's tortoise & hare
slow = fast = head
while fast and [Link]:
slow = [Link] # moves 1 step
fast = [Link] # moves 2 steps
if slow == fast:
return True # cycle detected
return False

def find_cycle_start(head):
slow = fast = head
while fast and [Link]:
slow, fast = [Link], [Link]
if slow == fast: # meeting point
 slow = head # reset one pointer to head
while slow != fast: # advance both 1 step
slow, fast = [Link], [Link]
return slow # cycle start
return None

Classic Problems
Problem Variant Complexity
Two Sum II (sorted array) Opposite direction O(n) time, O(1) space
3Sum Sort + outer loop + two pointers O(n²) time, O(1) space
Container With Most Water Opposite direction, maximize area O(n) time, O(1) space
Trapping Rain Water Precompute max from left & right O(n) time, O(1) space
Linked List Cycle Fast/slow — meet implies cycle O(n) time, O(1) space
Remove Duplicates (sorted) Same direction, write pointer O(n) time, O(1) space
Palindrome Check Opposite direction, compare chars O(n) time, O(1) space

⚡ Two Pointers — Interview Cheatsheet

• Prerequisite for opposite-direction: array must be SORTED (or problem gives sorted input)
• Same-direction (write pointer): left = slow writer, right = fast reader
• Fast/slow pointer: if they meet → cycle exists; reset one to head → find cycle start
• 3Sum: fix one element with outer loop, then two-pointer on remaining subarray
• Complexity: always O(n) — each pointer traverses the array at most once
 2 Sliding Window P1 — MUST MASTER ★ Rank 1

Maintain a contiguous subarray/substring of variable or fixed size. Instead of recomputing from scratch for each
window, update incrementally: add the new element entering the window, remove the element leaving it. Reduces
O(n²) brute force to O(n).

Fixed-Size Window Template

Python
def fixed_window(arr, k):
# Step 1: build first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Step 2: slide — add right element, remove left element
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # O(1) update
max_sum = max(max_sum, window_sum)
return max_sum

Variable-Size Window Template (Most Common)

Python
def variable_window(s, condition):
left = 0
result = 0
window_state = {} # track chars/counts in window

for right in range(len(s)):

# EXPAND: add s[right] to window
window_state[s[right]] = window_state.get(s[right], 0) + 1

# SHRINK: move left until window is valid

while not is_valid(window_state, condition):
window_state[s[left]] -= 1
if window_state[s[left]] == 0:
del window_state[s[left]]
left += 1

# UPDATE result (window [left..right] is now valid)

result = max(result, right - left + 1)

return result

Minimum Window Substring (Hard)

Python
from collections import Counter

def min_window(s, t):

need = Counter(t) # {char: count needed}
have = {} # {char: count in window}
formed = 0 # chars with satisfied count
 required = len(need)
left = 0
result = ''

for right in range(len(s)):

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

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

if not result or right - left + 1 < len(result):
result = s[left:right+1]
lc = s[left]
have[lc] -= 1
if lc in need and have[lc] < need[lc]:
formed -= 1
left += 1

return result

Problem Window Type Key Trick

Max sum subarray of size k Fixed Slide: add right, remove left
Longest substring without repeating Variable (max) Shrink when duplicate enters
Min window substring Variable (min) Expand until valid, shrink greedily
Longest substring with k distinct Variable (max) Shrink when distinct count > k
chars
Permutation in string Fixed = len(p) Compare char counts in window
Max consecutive ones III Variable (max) Count zeros; shrink when zeros > k

⚡ Sliding Window — Interview Cheatsheet

• Fixed window: precompute first window, then slide in O(1) per step
• Variable window: always expand right; shrink left only when constraint violated
• Use a hashmap/Counter to track window state in O(1)
• 'At most K distinct' → same template; maximize window size when count ≤ K
• Time: O(n) — each element enters and leaves the window exactly once
 3 Binary Search P1 — MUST MASTER ★ Rank 1

Eliminate half the search space with each comparison. Works on sorted arrays or any problem with a monotone
predicate (if condition holds at x, it holds for all values > x or < x). O(log n) per search.

Standard Template — Find Exact Value

Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # note: <= not <
mid = left + (right - left) // 2 # avoids integer overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # not found

Find Leftmost / Lower Bound

Python
def lower_bound(arr, target): # first index where arr[i] >= target
left, right = 0, len(arr)
while left < right: # note: < not <=
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid # don't exclude mid — may be the answer
return left # left == right == answer

def upper_bound(arr, target): # first index where arr[i] > target

left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left

Binary Search on Answer — Monotone Predicate

Python
# Pattern: 'find minimum X such that condition(X) is True'
# Condition must be monotone: False...False True...True

def binary_search_answer(lo, hi, condition):

result = hi
while lo <= hi:
mid = (lo + hi) // 2
 if condition(mid): # can we do better (smaller)?
result = mid
hi = mid - 1
else:
lo = mid + 1
return result

# Example: Koko eating bananas (LeetCode 875)

def min_eating_speed(piles, h):
def can_finish(speed):
return sum([Link](p / speed) for p in piles) <= h
return binary_search_answer(1, max(piles), can_finish)

Problem Search Space Key Insight

Search in rotated sorted array Array indices One half is always sorted — decide which
Find minimum in rotated array Array indices Min is at rotation point
Koko Eating Bananas Speed 1..max(piles) Monotone: faster speed → fewer hours
Capacity to ship packages in D Capacity range Monotone: more capacity → fewer days
days
Find peak element Array indices Move toward the higher neighbor
Sqrt(x) integer 0..x Binary search on answer
First bad version Version 1..n Find leftmost True

⚡ Binary Search — Interview Cheatsheet

• left <= right for exact search; left < right for bound-finding
• Always use mid = left + (right - left) // 2 to prevent overflow
• Binary search on answer: define a monotone condition → search on the answer space, not array
• Rotated array: check which half is sorted (compare arr[mid] to arr[left] or arr[right])
• When in doubt: visualize the condition as F...F T...T and find the first T
 4 DFS + Backtracking P1 — MUST MASTER ★ Rank 1

DFS explores as deep as possible along each branch before backtracking. Combined with backtracking, it
explores all possibilities (combinatorial search) while pruning branches that cannot yield valid solutions.

DFS on Graph / Tree

Python
def dfs(graph, node, visited):
if node in visited: return
[Link](node)
# process node
for neighbor in graph[node]:
dfs(graph, neighbor, visited)

# Iterative DFS (stack)

def dfs_iterative(graph, start):
stack, visited = [start], set()
while stack:
node = [Link]() # LIFO — goes deep
if node not in visited:
[Link](node)
[Link](graph[node]) # add neighbors

Backtracking Template — Permutations / Combinations

Python
def backtrack(candidates, start, path, result, target):
# BASE CASE: valid solution
if is_solution(path, target):
[Link](list(path)) # copy — don't append reference
return

# PRUNING: abandon branch early

if should_prune(path, target):
return

for i in range(start, len(candidates)):

[Link](candidates[i]) # CHOOSE
backtrack(candidates, i+1, path, result, target) # EXPLORE
[Link]() # UN-CHOOSE (backtrack)

# Permutations (order matters — start=0 each time, use 'used' set)

def permute(nums):
result, path, used = [], [], set()
def bt():
if len(path) == len(nums): [Link](list(path)); return
for i in range(len(nums)):
if i in used: continue
[Link](i); [Link](nums[i])
bt()
[Link](i); [Link]()
bt()
 return result

N-Queens — Classic Backtracking

Python
def solve_n_queens(n):
result = []
cols = set() # columns with queens
diag1 = set() # row - col (main diagonal)
diag2 = set() # row + col (anti-diagonal)

def bt(row, board):

if row == n:
[Link]([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # PRUNE
[Link](col); [Link](row-col); [Link](row+col)
board[row][col] = 'Q'
bt(row + 1, board) # EXPLORE next row
[Link](col); [Link](row-col); [Link](row+col)
board[row][col] = '.' # UNDO

bt(0, [['.']*n for _ in range(n)])

return result

⚡ Backtracking — Interview Cheatsheet

• Template: CHOOSE → EXPLORE → UN-CHOOSE (the three mandatory steps)
• Always copy the path when adding to results: [Link](list(path))
• Pruning makes backtracking practical — add early exit conditions
• Subsets (no order): pass start index; Permutations (order matters): use 'used' set
• To avoid duplicates in subsets with duplicate inputs: sort + skip same element at same level
• Time: O(n! or 2^n) worst case — acceptable only for small n (n ≤ ~20 in interviews)
 5 BFS (Breadth-First Search) P1 — MUST MASTER ★ Rank 1

Explores all nodes at distance d before any node at distance d+1. Uses a FIFO queue. Guarantees shortest path
in unweighted graphs. Also used for level-order tree traversal.

BFS Template — Shortest Path

Python
from collections import deque

def bfs(graph, start, end):

queue = deque([(start, 0)]) # (node, distance)
visited = {start}

while queue:
node, dist = [Link]() # FIFO — O(1) with deque
if node == end:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
[Link]((neighbor, dist + 1))
return -1 # unreachable

Multi-Source BFS (Walls and Gates / Rotten Oranges)

Python
def walls_and_gates(grid):
rows, cols = len(grid), len(grid[0])
INF = float('inf')
queue = deque()

# START: add ALL sources (gates = 0) simultaneously

for r in range(rows):
for c in range(cols):
if grid[r][c] == 0: # gate
[Link]((r, c))

dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = [Link]()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == INF:
grid[nr][nc] = grid[r][c] + 1
[Link]((nr, nc))
return grid

BFS — Level Order Tree Traversal

Python
def level_order(root):
 if not root: return []
queue = deque([root])
result = []
while queue:
level_size = len(queue) # snapshot size for this level
level = []
for _ in range(level_size):
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return result

Problem BFS Variant Key Insight

Shortest path in unweighted graph Standard BFS First visit = shortest path
Word Ladder BFS on word graph Each edge = one letter change
Rotten Oranges Multi-source BFS Start all sources simultaneously
01 Matrix (distance to nearest 0) Multi-source BFS Start from all 0s at once
Level order traversal BFS with level snapshot len(queue) at level start = level size
Number of Islands BFS/DFS flood fill Mark visited to avoid recount

⚡ BFS vs DFS — Interview Decision Guide

• Use BFS when: shortest path needed, level-by-level processing, minimum steps
• Use DFS when: full path exploration, cycle detection, topological sort, backtracking
• BFS space: O(width of tree/graph) — can be O(n) at widest level
• DFS space: O(depth) = O(h) for tree, O(n) worst case for graph
• Always use deque (not list) for queue — popleft() is O(1); [Link](0) is O(n)
 6 Dynamic Programming P1 — MUST MASTER ★ Rank 1

DP solves problems with overlapping subproblems and optimal substructure. Avoid recomputing the same
subproblem by storing results (memoization = top-down; tabulation = bottom-up). Converts exponential to
polynomial time.

Top-Down Memoization Template

Python
from functools import lru_cache

def dp_memoization(n):
@lru_cache(maxsize=None) # automatic memoization
def dp(i, state): # i = current index, state = relevant state
# BASE CASES
if i == 0: return base_value

# RECURRENCE: combine subproblem results

option1 = dp(i - 1, state_a) # don't take i
option2 = dp(i - 1, state_b) + value[i] # take i
return max(option1, option2)

return dp(n, initial_state)

Bottom-Up Tabulation Template

Python
def dp_tabulation(nums):
n = len(nums)
dp = [0] * (n + 1) # dp[i] = answer for first i elements

# BASE CASES
dp[0] = 0 # empty array
dp[1] = nums[0] # single element

# FILL TABLE: each cell depends on previous cells

for i in range(2, n + 1):
dp[i] = max(dp[i-1], # skip current
dp[i-2] + nums[i-1]) # take current (skip adjacent)
return dp[n]

# Space optimized (when only previous 1-2 cells needed):

def dp_space_optimized(nums):
prev2, prev1 = 0, 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1

Classic DP Patterns
DP Type Recurrence Problems
1D Linear dp[i] = f(dp[i-1], dp[i-2]) Climbing Stairs, House Robber, Fibonacci
Knapsack 0/1 dp[i][w] = max(skip, take) 0/1 Knapsack, Subset Sum, Partition
Equal Subset
Unbounded Knapsack dp[i] = max over all items Coin Change, Rod Cutting
LCS/Edit Distance dp[i][j] based on match LCS, Edit Distance, Longest Common
Substring
LIS dp[i] = max(dp[j]+1) for j<i Longest Increasing Subsequence
Matrix DP dp[i][j] = f(dp[i-1][j], dp[i][j-1]) Unique Paths, Minimum Path Sum
Interval DP dp[i][j] over ranges Burst Balloons, Matrix Chain Multiplication
State Machine dp[state] transitions Stock problems (hold/sold/cooldown)

⚡ DP — Interview Cheatsheet
• Ask: 'Does this problem have overlapping subproblems + optimal substructure?' → DP
• Define dp[i] clearly before coding: 'dp[i] = maximum profit using first i items'
• Identify recurrence by thinking: 'how does dp[i] relate to dp[i-1], dp[i-2]?'
• Top-down: easier to write; Bottom-up: easier to optimize space
• Space optimization: when dp[i] only needs dp[i-1] (or dp[i-1][j] and dp[i][j-1]), use rolling array
• Common mistake: off-by-one in base cases — carefully handle dp[0] and dp[1]
 7 Hashing (HashMap / HashSet) P1 — MUST MASTER ★ Rank 1

Trade space for time: store seen values in a hash table to achieve O(1) lookup. Converts O(n²) nested-loop
searches into O(n) single-pass algorithms. Most frequently applicable pattern in interviews.

Core Use Cases

Python
# 1. Two Sum — complement lookup
def two_sum(nums, target):
seen = {} # {value: index}
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) lookup
return [seen[complement], i]
seen[num] = i
return []

# 2. Frequency counting
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums) # {val: freq}
return sorted(count, key=[Link], reverse=True)[:k]

# 3. Grouping anagrams
def group_anagrams(strs):
groups = {}
for s in strs:
key = tuple(sorted(s)) # canonical form as key
[Link](key, []).append(s)
return list([Link]())

# 4. Sliding window + hashmap (seen + position)

def longest_no_repeat(s):
left, best, pos = 0, 0, {}
for right, c in enumerate(s):
if c in pos and pos[c] >= left:
left = pos[c] + 1
pos[c] = right
best = max(best, right - left + 1)
return best

Pattern Data Structure Examples

Complement search dict: val → index Two Sum, 4Sum
Frequency count Counter / dict Top K Frequent, Valid Anagram
Canonical grouping dict: key → list Group Anagrams, Isomorphic Strings
Seen / deduplicate set Contains Duplicate, Longest Consecutive
Prefix sum + hash dict: prefix → index Subarray Sum Equals K
Window state dict: char → count All Sliding Window problems

⚡ Hashing — Interview Cheatsheet

• Whenever you're doing 'find X such that X + current = target' → hashmap complement lookup
• Prefix sum + hashmap: for 'subarray with sum K', store {prefix_sum: count} → O(n)
• Canonical key trick: sort characters to group anagrams; tuple of char counts also works
• defaultdict(list) and Counter from collections save boilerplate
• Hash collision worst case: O(n) per lookup — always state O(1) average in interviews
 8 Heap / Priority Queue P1 — MUST MASTER ★ Rank 1

A heap maintains partial order to give O(log n) insert and O(log n) extract-min/max, with O(1) peek. Python's
heapq is a min-heap. Use negative values for max-heap. Essential for Top-K, scheduling, and stream problems.

Python heapq — Core Operations

Python
import heapq

# Min-heap operations
heap = []
[Link](heap, 5) # O(log n)
[Link](heap, 2)
[Link](heap, 8)
smallest = [Link](heap) # O(log n) → returns 2
peek = heap[0] # O(1) — don't pop
[Link]([3,1,4,1,5]) # O(n) — convert list in-place

# Max-heap: negate values

max_heap = []
[Link](max_heap, -10) # push negative
largest = -[Link](max_heap) # negate on pop

# Heap of tuples: (priority, value)

[Link](heap, (priority, item))

Top-K Elements
Python
def top_k_largest(nums, k): # O(n log k)
min_heap = []
for num in nums:
[Link](min_heap, num)
if len(min_heap) > k: # keep only k largest
[Link](min_heap) # removes smallest
return min_heap # k largest elements

def kth_largest(nums, k): # O(n log k)

return top_k_largest(nums, k)[0] # root = kth largest

# Alternative: use [Link] (internally uses a heap)

[Link](k, nums) # O(n log k)
[Link](k, nums) # O(n log k)

Merge K Sorted Lists

Python
def merge_k_lists(lists): # O(n log k)
heap = []
for i, node in enumerate(lists):
if node:
 [Link](heap, ([Link], i, node))

dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = [Link](heap)
[Link] = node
curr = [Link]
if [Link]:
[Link](heap, ([Link], i, [Link]))
return [Link]

⚡ Heap — Interview Cheatsheet

• Top-K largest: use a MIN-heap of size K (pop when > K; root = Kth largest)
• Top-K smallest: use a MAX-heap of size K (negate values)
• Median of data stream: two heaps — max-heap for lower half, min-heap for upper half
• [Link](k, iterable) is convenient for static arrays; heap is better for streams
• Always push tuples (priority, tiebreaker, item) to handle comparison for custom objects
• Build heap from list: [Link](arr) in O(n) — don't push one by one
 9 Union-Find (Disjoint Set Union) P1 — MUST MASTER ★ Rank 2

Tracks which elements belong to the same connected component. With path compression and union by rank,
find() and union() run in near O(1) amortized time (technically O(α(n)) where α is the inverse Ackermann function
— effectively constant).

Full Implementation with Path Compression + Union by Rank

Python
class UnionFind:
def __init__(self, n):
[Link] = list(range(n)) # parent[i] = i initially
[Link] = [0] * n # rank = tree height estimate
[Link] = n # number of components

def find(self, x): # O(α(n)) ≈ O(1)

if [Link][x] != x:
[Link][x] = [Link]([Link][x]) # PATH COMPRESSION
return [Link][x]

def union(self, x, y): # O(α(n)) ≈ O(1)

rx, ry = [Link](x), [Link](y)
if rx == ry: return False # already same component
# UNION BY RANK: attach smaller tree under larger
if [Link][rx] < [Link][ry]: rx, ry = ry, rx
[Link][ry] = rx
if [Link][rx] == [Link][ry]: [Link][rx] += 1
[Link] -= 1
return True # merged successfully

def connected(self, x, y):

return [Link](x) == [Link](y)

# Number of Islands using Union-Find

def num_islands(grid):
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
for dr, dc in [(0,1),(1,0)]: # only right and down
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]=='1':
if [Link](r*cols+c, nr*cols+nc): count -= 1
return count

⚡ Union-Find — Interview Cheatsheet

• Two optimizations are BOTH required for near-O(1): path compression + union by rank
• Path compression: make every node on the find path point directly to root
• Union by rank: always attach the shorter tree under the taller tree
• Key use cases: number of connected components, cycle detection in undirected graphs, Kruskal's MST
• vs BFS/DFS: DSU is better for dynamic connectivity (edges added over time); BFS/DFS for static
graphs
 10 Monotonic Stack P1 — MUST MASTER ★ Rank 2

A stack that maintains elements in monotonically increasing or decreasing order. When a new element violates
the order, pop elements and process them. Reduces O(n²) comparison problems to O(n) — each element is
pushed and popped at most once.

Next Greater Element Template

Python
def next_greater_element(nums): # O(n)
n = len(nums)
result = [-1] * n
stack = [] # stores indices, decreasing values

for i in range(n):
# Pop all elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = [Link]()
result[idx] = nums[i] # nums[i] is the next greater for nums[idx]
[Link](i)
return result
# Remaining elements in stack have no next greater → stay -1

# Circular array: iterate twice (i % n)

def next_greater_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n): # two passes
while stack and nums[stack[-1]] < nums[i % n]:
result[[Link]()] = nums[i % n]
if i < n: [Link](i)
return result

Largest Rectangle in Histogram

Python
def largest_rectangle(heights): # O(n)
stack = [] # increasing stack of indices
max_area = 0
[Link](0) # sentinel to flush stack at end

for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[[Link]()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
[Link](i)

return max_area

Problem Stack Order Pop Condition

Next Greater Element Decreasing values Pop when current > stack top
Next Smaller Element Increasing values Pop when current < stack top
Largest Rectangle in Histogram Increasing heights Pop when current height < top
Trapping Rain Water Decreasing heights Pop and compute water trapped
Daily Temperatures Decreasing values Pop when warmer day found
Sum of Subarray Minimums Increasing values Pop to compute contribution

⚡ Monotonic Stack — Interview Cheatsheet

• Increasing stack: pop when current is SMALLER → used for 'next smaller element'
• Decreasing stack: pop when current is LARGER → used for 'next greater element'
• Every element enters and exits the stack exactly once → O(n) total
• Sentinel trick: append 0 to heights array to force flush all remaining stack elements
• Think: 'for each element, what is the nearest element to its left/right that is greater/smaller?'
 P2 — HIGH PRIORITY PATTERNS

11 Trie (Prefix Tree) P2 — HIGH PRIORITY ★ Rank 2

A tree where each path from root to a node spells a prefix. Look up any word/prefix in O(word length) time —
independent of dictionary size. Essential for autocomplete, spell check, and IP routing.

Trie Implementation
Python
class TrieNode:
def __init__(self):
[Link] = {} # char → TrieNode
self.is_end = False # True if valid word ends here

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

def insert(self, word): # O(len(word))

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

def search(self, word): # O(len(word))

node = self._traverse(word)
return node is not None and node.is_end

def starts_with(self, prefix): # O(len(prefix))

return self._traverse(prefix) is not None

def _traverse(self, s):

node = [Link]
for ch in s:
if ch not in [Link]: return None
node = [Link][ch]
return node

⚡ Trie — Interview Cheatsheet

• Trie vs HashSet: Trie supports prefix queries in O(L); HashSet only supports exact match
• Trie vs Binary Search on sorted list: Trie O(L) vs O(L log n) for prefix search
• Space: O(ALPHABET_SIZE × N × L) worst case — can be large; dict-based children saves space
• Common extensions: add count (word frequency), add delete, add wildcard search (.)
• Word Search II (LeetCode Hard): build Trie from word list, then DFS on board — O(4^(m*n) × L) pruned
 12 Greedy P1 — MUST MASTER ★ Rank 2

Make the locally optimal choice at each step. Valid when the problem has the greedy choice property: a local
optimum leads to a global optimum. Greedy is faster than DP but doesn't always work — you must prove or intuit
why greedy is correct.

Jump Game — Greedy

Python
def can_jump(nums): # Can you reach the last index?
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: return False # stuck — can't move forward
max_reach = max(max_reach, i + jump)
return True

def jump_game_ii(nums): # Minimum jumps to reach end

jumps = cur_end = cur_far = 0
for i in range(len(nums) - 1):
cur_far = max(cur_far, i + nums[i]) # farthest reachable from here
if i == cur_end: # reached end of current jump range
jumps += 1
cur_end = cur_far # extend range
return jumps

Activity Selection / Interval Scheduling

Python
def max_non_overlapping_intervals(intervals): # O(n log n)
# Greedy: always pick interval with EARLIEST END TIME
[Link](key=lambda x: x[1]) # sort by end time
count, last_end = 0, float('-inf')
for start, end in intervals:
if start >= last_end: # no overlap with last selected
count += 1
last_end = end
return count

# Proof: earliest end time leaves maximum room for future intervals

Problem Greedy Choice Why it Works

Jump Game II Extend farthest reach per jump Greedy maximizes options at each step
Activity Selection Pick earliest end time Minimizes time blocked for future choices
Fractional Knapsack Highest value/weight ratio Partial items allowed — no trade-off
Huffman Encoding Merge two smallest freq nodes Optimal prefix-free code
Candy (children) Two passes: left & right rules Each rule satisfied without conflict
Assign Cookies Sort + greedy match Smallest sufficient cookie satisfies
greediest child

⚡ Greedy — Interview Cheatsheet

• Greedy works when: greedy choice property + optimal substructure
• Always ask: 'Why is the greedy choice safe here?' — be ready to explain
• Common greedy strategies: sort by end time (intervals), sort by ratio (knapsack), scan left-right
• Greedy fails for: 0/1 Knapsack, Coin Change with arbitrary denominations → use DP instead
• Exchange argument proof: assume an optimal solution differs → swap greedy choice → still optimal
 13 Backtracking P2 — HIGH PRIORITY ★ Rank 2

Systematic exhaustive search with pruning. Build a solution incrementally; abandon ('backtrack') when a partial
solution cannot lead to a valid complete solution. Reviewed separately from DFS because the template and
pruning logic are distinct.

Subsets — Include/Exclude Pattern

Python
def subsets(nums): # all 2^n subsets
result = []
def bt(start, path):
[Link](list(path)) # every partial path is a valid subset
for i in range(start, len(nums)):
[Link](nums[i])
bt(i + 1, path) # i+1: no reuse of same element
[Link]()
bt(0, [])
return result

def subsets_with_dups(nums): # deduplicate with sorted input

[Link]()
result = []
def bt(start, path):
[Link](list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue # skip dup
[Link](nums[i])
bt(i + 1, path)
[Link]()
bt(0, [])
return result

Combination Sum
Python
def combination_sum(candidates, target): # elements reusable
result = []
def bt(start, path, remaining):
if remaining == 0:
[Link](list(path))
return
if remaining < 0: return # PRUNE: exceeded target
for i in range(start, len(candidates)):
[Link](candidates[i])
bt(i, path, remaining - candidates[i]) # i (not i+1) → reuse allowed
[Link]()
bt(0, [], target)
return result

⚡ Backtracking Template Summary

• Subsets (no dups): bt(i+1, path) — advance start
• Subsets (with dups): sort first, then skip if nums[i] == nums[i-1] and i > start
• Combinations reuse allowed: bt(i, path) — don't advance start
• Permutations: bt(0, path, used_set) — restart from 0, track used indices
• Time complexity: O(2^n) for subsets, O(n!) for permutations, O(n^target) for combo sum
 14 Topological Sort P2 — HIGH PRIORITY ★ Rank 3

Linear ordering of nodes in a DAG (Directed Acyclic Graph) such that for every edge u→v, u appears before v.
Used for dependency resolution, build systems, and course scheduling. Two algorithms: Kahn's (BFS) and DFS-
based.

Kahn's Algorithm — BFS-based

Python
from collections import deque

def topo_sort_kahn(n, edges): # n nodes, edges = [(u,v), ...]

in_degree = [0] * n
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1

queue = deque(i for i in range(n) if in_degree[i] == 0)

order = []

while queue:
node = [Link]()
[Link](node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
[Link](neighbor)

return order if len(order) == n else [] # empty list = cycle detected

# Course Schedule (LeetCode 207)

def can_finish(num_courses, prerequisites):
return len(topo_sort_kahn(num_courses, prerequisites)) == num_courses

⚡ Topological Sort — Interview Cheatsheet

• Kahn's (BFS): start with nodes of in-degree 0 → remove node → update neighbors
• DFS-based: post-order DFS → push to stack after processing all children → reverse stack
• Cycle detection: if topological order contains fewer than n nodes → cycle exists
• Use cases: course scheduling, build dependencies, task ordering, git commit ancestry
• Only valid for DAGs — check for cycle before applying to general directed graphs
 15 Sorting as Preprocessing P2 — HIGH PRIORITY ★ Rank 3

Sorting transforms an unsorted problem into one where greedy or binary search solutions become applicable. O(n
log n) sort is often worth it if it reduces subsequent logic from O(n²) to O(n).

Sort + Two Pointers — 3Sum

Python
def three_sum(nums): # O(n²)
[Link]() # SORT FIRST
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dup
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 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 total < 0: left += 1
else: right -= 1
return result

Sort key Enables Example

Sort by value Binary search, two pointers Two Sum II, 3Sum, Search Insert Position
Sort by start time Merge intervals Merge Intervals, Meeting Rooms
Sort by end time Activity selection greedy Non-overlapping Intervals
Sort by custom key Greedy ordering proofs Largest Number (compare concatenation)
Sort + index track Inverse operations Sort Colors (Dutch flag), Relative Ranks

16 Prefix Sum P2 — HIGH PRIORITY ★ Rank 3

Precompute cumulative sums so any range sum query is answered in O(1). Combine with a hashmap to find
subarrays with a target sum in O(n).

1D Prefix Sum
Python
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, v in enumerate(arr):
prefix[i+1] = prefix[i] + v
return prefix

# Range sum query: sum(arr[l..r]) = prefix[r+1] - prefix[l] → O(1)

# Subarray Sum Equals K (LeetCode 560) — O(n)

def subarray_sum(nums, k):
count = 0
prefix = 0
seen = {0: 1} # {prefix_sum: frequency}
for num in nums:
prefix += num
count += [Link](prefix - k, 0) # complement lookup
seen[prefix] = [Link](prefix, 0) + 1
return count

# 2D Prefix Sum
def build_2d_prefix(matrix):
rows, cols = len(matrix), len(matrix[0])
P = [[0]*(cols+1) for _ in range(rows+1)]
for r in range(1, rows+1):
for c in range(1, cols+1):
P[r][c] = (matrix[r-1][c-1]
+ P[r-1][c] + P[r][c-1] - P[r-1][c-1])
return P
# Query: sum(r1,c1)→(r2,c2) = P[r2+1][c2+1]-P[r1][c2+1]-P[r2+1][c1]+P[r1][c1]

⚡ Prefix Sum — Interview Cheatsheet

• Range sum in O(1) after O(n) preprocessing — use when multiple range queries needed
• Subarray with sum K: store {prefix_sum: count}; at each step check if (prefix - k) was seen
• Handles negative numbers (unlike sliding window which requires all-positive for sum problems)
• 2D prefix sum: sum of rectangle in O(1) — inclusion-exclusion formula
• Variation: prefix XOR (find subarray with XOR = k), prefix product
 17 Divide and Conquer P2 — HIGH PRIORITY ★ Rank 3

Split the problem into smaller subproblems of the same type, solve recursively, then combine results. Classic
examples: Merge Sort, Quick Sort, binary search, and counting inversions.

Merge Sort (Canonical D&C)

Python
def merge_sort(arr): # O(n log n) time, O(n) space
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # DIVIDE
right = merge_sort(arr[mid:]) # DIVIDE
return merge(left, right) # COMBINE

def merge(left, right):

result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: [Link](left[i]); i += 1
else: [Link](right[j]); j += 1
return result + left[i:] + right[j:]

# Count inversions: in merge step, when right[j] < left[i]

# all remaining elements in left are also > right[j]
# inversions += len(left) - i

Problem D&C Strategy Complexity

Merge Sort Split, sort halves, merge O(n log n) time, O(n) space
Quick Sort Partition around pivot, recurse O(n log n) avg, O(n²) worst
Binary Search Eliminate half search space O(log n)
Count Inversions Merge sort + count during merge O(n log n)
Maximum Subarray (D&C) Split, find crossing max, combine O(n log n) — Kadane's is O(n)
Closest Pair of Points Split by x, recurse, merge strip O(n log n)

18 Merge Intervals P2 — HIGH PRIORITY ★ Rank 3

Sort intervals by start time, then greedily merge overlapping ones. A fundamental pattern for any problem
involving time ranges, calendar events, or resource allocation.

Merge Intervals
Python
def merge_intervals(intervals): # O(n log n)
[Link](key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps with last merged
merged[-1][1] = max(merged[-1][1], end) # extend end
 else:
[Link]([start, end]) # no overlap — new interval
return merged

def insert_interval(intervals, new_interval):

result = []
i, start, end = 0, new_interval[0], new_interval[1]
# Add all intervals ending before new_interval starts
while i < len(intervals) and intervals[i][1] < start:
[Link](intervals[i]); i += 1
# Merge all overlapping intervals
while i < len(intervals) and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
[Link]([start, end])
# Add remaining
[Link](intervals[i:])
return result

⚡ Merge Intervals — Interview Cheatsheet

• Always sort by start time first — this is the mandatory first step
• Overlap condition: [Link] <= last_merged.end
• Merge: new end = max(last_merged.end, [Link]) — don't just overwrite!
• Meeting Rooms II (min rooms needed): use two sorted arrays (starts, ends) + two pointers
• Insert Interval: three phases — add non-overlapping left, merge overlapping, add non-overlapping right
 19 Tree Traversal P2 — HIGH PRIORITY ★ Rank 3

Almost all binary tree problems reduce to a traversal variant. Master the three DFS orders (inorder, preorder,
postorder) both recursively and iteratively, plus BFS level-order. The choice of traversal determines what
information is available when visiting a node.

Universal Recursive Template

Python
def solve_tree(root):
if not root: return base_value # handle None

# Preorder: process node BEFORE subtrees

# preorder_action([Link])

left_result = solve_tree([Link])
right_result = solve_tree([Link])

# Postorder: process node AFTER subtrees (most common for return-value problems)
# return combine(left_result, right_result, [Link])

# Inorder: process node BETWEEN subtrees

# inorder_action([Link])

Key Tree Problems with Traversal Strategy

Python
# MAX DEPTH — postorder (need children's depths first)
def max_depth(root):
if not root: return 0
return 1 + max(max_depth([Link]), max_depth([Link]))

# DIAMETER — postorder, track globally

def diameter(root):
self_max = [0]
def depth(node):
if not node: return 0
l, r = depth([Link]), depth([Link])
self_max[0] = max(self_max[0], l + r) # diameter through this node
return 1 + max(l, r) # height for parent
depth(root)
return self_max[0]

# LOWEST COMMON ANCESTOR

def lca(root, p, q):
if not root or root == p or root == q: return root
left = lca([Link], p, q)
right = lca([Link], p, q)
if left and right: return root # p in one subtree, q in other
return left or right # both in same subtree

# VALIDATE BST — inorder with bounds

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
 if not root: return True
if not (lo < [Link] < hi): return False
return (is_valid_bst([Link], lo, [Link]) and
is_valid_bst([Link], [Link], hi))

Problem Traversal Key Return Value

Max/Min Depth Postorder height (int)
Diameter of tree Postorder + global max height; update global
Path Sum (root to leaf) Preorder remaining target
Lowest Common Ancestor Postorder found node or None
Validate BST Preorder with bounds bool
Serialize/Deserialize Preorder encoded string
Right side view BFS level order last node at each level
Symmetric tree Simultaneous left+right bool mirror check
DFS

⚡ Tree Traversal — Interview Cheatsheet

• Postorder (L→R→Node): use when you need results from both subtrees before processing current
node
• Preorder (Node→L→R): use when parent information must be passed DOWN to children
• Inorder (L→Node→R): use for BST problems — inorder of BST = sorted sequence
• Always handle the None (base) case first — return appropriate identity value (0, True, None, inf)
• Global variable trick: use nonlocal or a mutable container [0] to track cross-subtree results
• For 'path' problems: pass remaining sum down; for 'height' problems: return and combine upward
 MASTER CHEAT SHEET — PATTERN RECOGNITION GUIDE

How to Identify the Right Pattern

If the problem says / gives you... Think... Pattern
Sorted array, find pair/triplet with sum Two pointers Two Pointers
Subarray/substring with condition Shrink/expand window Sliding Window
Sorted array, large n, O(log n) required Binary search Binary Search
'Find minimum X such that...' (monotone) Binary search on answer Binary Search
All permutations / combinations / subsets Build + undo Backtracking
Shortest path, minimum steps, unweighted Level by level BFS
All paths, cycle detection, flood fill Go deep DFS
Overlapping subproblems, optimal choice Store & reuse Dynamic Programming
Count/find in O(1), avoid nested loops Store seen values Hashing
Top-K, K smallest/largest, stream data Heap of size K Heap
Connected components, union operations DSU Union-Find
Next greater/smaller element, O(n) Monotone stack Monotonic Stack
Prefix queries, autocomplete, word search Trie Trie
Local optimal = global optimal Greedy Greedy
Dependencies, ordering, DAG Topo sort Topological Sort
Range sum queries, subarray sum = K Precompute prefix Prefix Sum
Intervals, meeting rooms, time ranges Sort + sweep Merge Intervals
Binary tree problem (any) Postorder DFS Tree Traversal
Large n, T(n) = 2T(n/2) + O(n) Split + merge Divide and Conquer

Complexity Quick Reference

Pattern Time Space
Two Pointers O(n) O(1)
Sliding Window O(n) O(k) window state
Binary Search O(log n) O(1)
DFS / BFS O(V + E) O(V)
Backtracking (subsets) O(2^n) O(n) stack
Backtracking (permutations) O(n!) O(n) stack
Dynamic Programming O(n × states) O(n × states)
Hashing O(n) average O(n)
Heap (Top-K) O(n log k) O(k)
Union-Find O(α(n)) ≈ O(1) O(n)
Monotonic Stack O(n) O(n)
Trie insert/search O(L) O(ALPHA × N × L)
Topological Sort O(V + E) O(V)
Prefix Sum O(n) build, O(1) query O(n)
Merge Intervals O(n log n) O(n)
Merge Sort / D&C O(n log n) O(n)

Recognize the pattern → apply the template → optimize. Repeat daily. You've got this!