DSA Coding Patterns Python Cheatsheet
DSA Coding Patterns — Python Cheatsheet
A pattern-first reference. Each section: when to reach for it, a template, complexity, and classic problems.
Contents
- Pattern recognition table
- Complexity reference
- Two Pointers
- Sliding Window
- Prefix Sum & Difference Array
- Binary Search
- Cyclic Sort / Index-as-Hash
- Intervals & Line Sweep
- Matrix Traversal
- Monotonic Stack
- Monotonic Deque
- Fast & Slow Pointers
- Linked Lists
- Trees — DFS
- Trees — BFS
- Binary Search Trees
- Trie
- Heaps / Top-K / Two Heaps
- Graphs — Traversal
- Topological Sort
- Union-Find (DSU)
- Shortest Paths
- Minimum Spanning Tree
- Backtracking
- Dynamic Programming
- Greedy
- Bit Manipulation
- Math & Number Theory
- Fenwick Tree & Segment Tree
- String Algorithms
- Design Problems
- Selection & Sampling
- Python toolkit for interviews
0. Pattern recognition table
| Signal in the problem | Reach for |
|---|---|
| Sorted array, find pair/triplet | Two pointers |
| "Longest/shortest subarray or substring with…" | Sliding window |
| Range sum queries, immutable array | Prefix sum |
| Range updates, then read once | Difference array |
| Sorted input, or "minimize the maximum" | Binary search (incl. on answer) |
| Array holds 1..n, find missing/duplicate | Cyclic sort |
| Overlapping ranges, meetings | Sort + merge / line sweep |
| Cycle in linked list, find middle | Fast & slow pointers |
| "Next greater/smaller element", histogram | Monotonic stack |
| Sliding window max/min | Monotonic deque |
| Top K, Kth largest, merge K lists | Heap |
| Running median | Two heaps |
| Prefix matching, autocomplete | Trie |
| Dependencies, ordering, prerequisites | Topological sort |
| Connectivity, "number of groups", dynamic merging | Union-Find |
| Shortest path, weighted | Dijkstra / Bellman-Ford |
| Shortest path, unweighted | BFS |
| All subsets/permutations/combinations | Backtracking |
| Count ways / optimal value with overlapping subproblems | DP |
| Locally optimal choice provably safe | Greedy |
| n ≤ 20, subsets of a set | Bitmask |
| Substring search | KMP / Rabin-Karp |
1. Complexity reference
| n | Acceptable complexity |
|---|---|
| ≤ 10 | O(n!) |
| ≤ 20 | O(2ⁿ · n) |
| ≤ 100 | O(n⁴) |
| ≤ 1,000 | O(n³) |
| ≤ 10,000 | O(n²) |
| ≤ 10⁶ | O(n log n) |
| ≤ 10⁸ | O(n) |
Python-specific costs: list.pop(0) is O(n) — use collections.deque. String concatenation in a loop is O(n²) — build a list and "".join(). in on a list is O(n), on a set/dict O(1).
2. Two Pointers
Use when: input is sorted (or can be), and you need pairs/triplets, in-place partitioning, or comparison from both ends.
# Opposite ends: pair with given sum in a sorted array
def two_sum_sorted(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return [lo, hi]
if s < target:
lo += 1
else:
hi -= 1
return [-1, -1]
# Triplets summing to zero: fix one, two-pointer the rest
def three_sum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
if nums[i] > 0:
break
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1
return res
# Same direction (read/write): stable in-place removal
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write
# Two sequences: is s a subsequence of t?
def is_subsequence(s, t):
i = 0
for ch in t:
if i < len(s) and s[i] == ch:
i += 1
return i == len(s)
Complexity: O(n) after an O(n log n) sort. Problems: Two Sum II, 3Sum, 4Sum, Container With Most Water, Trapping Rain Water, Sort Colors, Remove Duplicates, Valid Palindrome, Merge Sorted Array (fill from the back).
3. Sliding Window
Use when: contiguous subarray/substring with a constraint. Grow the right edge; shrink the left edge while the window is invalid.
# Fixed size k
def max_sum_window_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
# Variable size — longest valid window
from collections import defaultdict
def longest_substring_k_distinct(s, k):
count = defaultdict(int)
left = best = 0
for right, ch in enumerate(s):
count[ch] += 1
while len(count) > k: # invalid -> shrink
out = s[left]
count[out] -= 1
if count[out] == 0:
del count[out]
left += 1
best = max(best, right - left + 1)
return best
# Variable size — shortest valid window
def min_subarray_len(target, nums):
left = total = 0
best = float('inf')
for right, v in enumerate(nums):
total += v
while total >= target: # valid -> record, then shrink
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == float('inf') else best
# Minimum window substring (all chars of t, with multiplicity)
from collections import Counter
def min_window(s, t):
if not t or not s:
return ""
need = Counter(t)
missing = len(t)
left = 0
best = (float('inf'), 0, 0)
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
while missing == 0:
if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]
# "At most K" trick: exactly K = atMost(K) - atMost(K-1)
def subarrays_with_k_distinct(nums, k):
def at_most(m):
count = defaultdict(int)
left = res = 0
for right, v in enumerate(nums):
count[v] += 1
while len(count) > m:
count[nums[left]] -= 1
if count[nums[left]] == 0:
del count[nums[left]]
left += 1
res += right - left + 1 # all windows ending at right
return res
return at_most(k) - at_most(k - 1)
Complexity: O(n) — each pointer moves forward only. Problems: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum, Permutation in String, Find All Anagrams, Longest Repeating Character Replacement, Fruit Into Baskets, Sliding Window Maximum (see deque), Max Consecutive Ones III.
Caution: windows require monotonicity — adding elements must only make the window "more invalid." With negative numbers and a sum target, use prefix sums + hashmap instead.
4. Prefix Sum & Difference Array
Use when: many range-sum queries (prefix sum), or many range updates followed by one read (difference array).
# Immutable range sums
class PrefixSum:
def __init__(self, nums):
self.pre = [0] * (len(nums) + 1)
for i, v in enumerate(nums):
self.pre[i + 1] = self.pre[i] + v
def range_sum(self, i, j): # inclusive
return self.pre[j + 1] - self.pre[i]
# Count subarrays summing to k (works with negatives)
def subarray_sum_equals_k(nums, k):
seen = defaultdict(int)
seen[0] = 1
running = res = 0
for v in nums:
running += v
res += seen[running - k]
seen[running] += 1
return res
# Longest subarray with sum k -> store first index of each prefix
def longest_subarray_sum_k(nums, k):
first = {0: -1}
running = best = 0
for i, v in enumerate(nums):
running += v
if running - k in first:
best = max(best, i - first[running - k])
if running not in first:
first[running] = i
return best
# Prefix XOR: count subarrays with XOR == k (same shape, swap + for ^)
def subarray_xor_k(nums, k):
seen = defaultdict(int)
seen[0] = 1
cur = res = 0
for v in nums:
cur ^= v
res += seen[cur ^ k]
seen[cur] += 1
return res
# Difference array: add val to [l, r] many times, O(1) each
def range_updates(n, updates):
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r + 1] -= val
out, run = [], 0
for i in range(n):
run += diff[i]
out.append(run)
return out
# 2-D prefix sum
def build_2d(mat):
m, n = len(mat), len(mat[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
pre[i + 1][j + 1] = (mat[i][j] + pre[i][j + 1]
+ pre[i + 1][j] - pre[i][j])
return pre
def region_sum(pre, r1, c1, r2, c2):
return (pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1]
- pre[r2 + 1][c1] + pre[r1][c1])
Problems: Range Sum Query, Subarray Sum Equals K, Continuous Subarray Sum, Product of Array Except Self, Corporate Flight Bookings, Car Pooling, Maximum Subarray (Kadane), Contiguous Array.
5. Binary Search
Use when: sorted data, or the answer space is monotonic ("if X works, X+1 works").
# Canonical lower/upper bound — the two you should memorize
def lower_bound(a, target): # first index with a[i] >= target
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(a, target): # first index with a[i] > target
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= target:
lo = mid + 1
else:
hi = mid
return lo
# Standard library equivalents:
# bisect.bisect_left == lower_bound
# bisect.bisect_right == upper_bound
# count of x = bisect_right(a, x) - bisect_left(a, x)
# Rotated sorted array
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Minimum of rotated sorted array (no duplicates)
def find_min_rotated(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
# BINARY SEARCH ON THE ANSWER — the high-value variant
# "Minimize the maximum load" / "smallest capacity that finishes in D days"
def ship_within_days(weights, days):
def feasible(cap):
need, cur = 1, 0
for w in weights:
if cur + w > cap:
need += 1
cur = 0
cur += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
# Peak element (unsorted but locally monotonic)
def find_peak(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo
# Real-valued search: iterate a fixed number of times
def sqrt_float(x, iters=100):
lo, hi = 0.0, max(1.0, x)
for _ in range(iters):
mid = (lo + hi) / 2
if mid * mid < x:
lo = mid
else:
hi = mid
return lo
Complexity: O(log n), or O(n log(range)) when searching on the answer. Problems: Search Insert Position, Search in Rotated Sorted Array I/II, Find First and Last Position, Koko Eating Bananas, Split Array Largest Sum, Capacity to Ship Packages, Median of Two Sorted Arrays, Kth Smallest in Sorted Matrix, Minimum Days to Make Bouquets.
Invariant discipline: pick while lo < hi with hi = mid / lo = mid + 1 and never write hi = mid - 1 in the same loop. Mixing the two forms is the usual source of off-by-one bugs.
6. Cyclic Sort / Index-as-Hash
Use when: array contains numbers in a known small range (typically 1..n or 0..n-1) and you need missing/duplicate/misplaced values in O(1) extra space.
def cyclic_sort(nums): # values 1..n
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
return nums
def find_missing_after_sort(nums):
cyclic_sort(nums)
return [i + 1 for i, v in enumerate(nums) if v != i + 1]
# Negation marking (values 1..n, mutate signs as visited flags)
def find_disappeared_numbers(nums):
for v in nums:
idx = abs(v) - 1
if nums[idx] > 0:
nums[idx] = -nums[idx]
return [i + 1 for i, v in enumerate(nums) if v > 0]
# First missing positive
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
Problems: Missing Number, Find All Numbers Disappeared, Find the Duplicate Number, Find All Duplicates, Set Mismatch, First Missing Positive.
7. Intervals & Line Sweep
Use when: ranges that may overlap; scheduling; "how many at once."
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
out = []
for start, end in intervals:
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end)
else:
out.append([start, end])
return out
def insert_interval(intervals, new):
out, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
out.append(intervals[i]); i += 1
s, e = new
while i < n and intervals[i][0] <= e:
s = min(s, intervals[i][0])
e = max(e, intervals[i][1])
i += 1
out.append([s, e])
out.extend(intervals[i:])
return out
def interval_intersection(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
lo = max(a[i][0], b[j][0])
hi = min(a[i][1], b[j][1])
if lo <= hi:
out.append([lo, hi])
if a[i][1] < b[j][1]:
i += 1
else:
j += 1
return out
# Minimum rooms / max concurrent — heap of end times
import heapq
def min_meeting_rooms(intervals):
intervals.sort(key=lambda x: x[0])
ends = []
for s, e in intervals:
if ends and ends[0] <= s:
heapq.heappop(ends)
heapq.heappush(ends, e)
return len(ends)
# Line sweep — same answer, and gives the timeline
def max_concurrent(intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1)) # end before start at same time
events.sort()
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
# Non-overlapping intervals to remove (greedy by earliest end)
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1])
count, prev_end = 0, float('-inf')
for s, e in intervals:
if s >= prev_end:
prev_end = e
else:
count += 1
return count
Problems: Merge Intervals, Insert Interval, Non-overlapping Intervals, Meeting Rooms I/II, Interval List Intersections, My Calendar, Employee Free Time, Minimum Number of Arrows.
8. Matrix Traversal
DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS8 = DIRS4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))
def neighbors(r, c, m, n, dirs=DIRS4):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
yield nr, nc
def spiral_order(mat):
if not mat:
return []
top, bottom = 0, len(mat) - 1
left, right = 0, len(mat[0]) - 1
out = []
while top <= bottom and left <= right:
for c in range(left, right + 1):
out.append(mat[top][c])
top += 1
for r in range(top, bottom + 1):
out.append(mat[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
out.append(mat[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
out.append(mat[r][left])
left += 1
return out
def rotate_90_clockwise(mat): # in place: transpose + reverse rows
n = len(mat)
for i in range(n):
for j in range(i + 1, n):
mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
for row in mat:
row.reverse()
return mat
def set_zeroes(mat): # O(1) space, use row 0 / col 0 as flags
m, n = len(mat), len(mat[0])
first_col = any(mat[i][0] == 0 for i in range(m))
first_row = any(mat[0][j] == 0 for j in range(n))
for i in range(1, m):
for j in range(1, n):
if mat[i][j] == 0:
mat[i][0] = mat[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if mat[i][0] == 0 or mat[0][j] == 0:
mat[i][j] = 0
if first_row:
for j in range(n):
mat[0][j] = 0
if first_col:
for i in range(m):
mat[i][0] = 0
return mat
Problems: Spiral Matrix, Rotate Image, Set Matrix Zeroes, Search a 2D Matrix, Diagonal Traverse, Game of Life, Number of Islands, Rotting Oranges.
9. Monotonic Stack
Use when: "next/previous greater or smaller element," histogram areas, or you need to pop dominated candidates.
def next_greater_element(nums):
res = [-1] * len(nums)
stack = [] # indices, values decreasing
for i, v in enumerate(nums):
while stack and nums[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return res
def daily_temperatures(temps):
res = [0] * len(temps)
stack = []
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
res[j] = i - j
stack.append(i)
return res
def largest_rectangle_histogram(heights):
stack = [] # increasing heights
best = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
def trapping_rain_water(height): # two pointers variant, O(1) space
if not height:
return 0
lo, hi = 0, len(height) - 1
left_max, right_max, total = height[lo], height[hi], 0
while lo < hi:
if left_max <= right_max:
lo += 1
left_max = max(left_max, height[lo])
total += left_max - height[lo]
else:
hi -= 1
right_max = max(right_max, height[hi])
total += right_max - height[hi]
return total
def remove_k_digits(num, k): # smallest number after removing k
stack = []
for ch in num:
while k and stack and stack[-1] > ch:
stack.pop()
k -= 1
stack.append(ch)
result = "".join(stack[:len(stack) - k]).lstrip("0")
return result or "0"
Rule of thumb: for next greater, keep the stack decreasing and pop on a bigger incoming value. Flip the comparison for next smaller. Problems: Daily Temperatures, Next Greater Element I/II, Largest Rectangle in Histogram, Maximal Rectangle, Trapping Rain Water, Remove K Digits, Sum of Subarray Minimums, Car Fleet, Valid Parentheses (plain stack).
10. Monotonic Deque
Use when: min/max over a sliding window.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # indices, values decreasing
out = []
for i, v in enumerate(nums):
while dq and nums[dq[-1]] <= v:
dq.pop()
dq.append(i)
if dq[0] <= i - k: # left of window
dq.popleft()
if i >= k - 1:
out.append(nums[dq[0]])
return out
# Longest subarray where max - min <= limit
def longest_subarray_within_limit(nums, limit):
max_dq, min_dq = deque(), deque()
left = best = 0
for right, v in enumerate(nums):
while max_dq and nums[max_dq[-1]] <= v:
max_dq.pop()
max_dq.append(right)
while min_dq and nums[min_dq[-1]] >= v:
min_dq.pop()
min_dq.append(right)
while nums[max_dq[0]] - nums[min_dq[0]] > limit:
if max_dq[0] == left:
max_dq.popleft()
if min_dq[0] == left:
min_dq.popleft()
left += 1
best = max(best, right - left + 1)
return best
Problems: Sliding Window Maximum, Shortest Subarray with Sum at Least K, Longest Continuous Subarray with Absolute Diff ≤ Limit, Jump Game VI, Constrained Subsequence Sum.
11. Fast & Slow Pointers
Use when: cycle detection in a linked list or in a functional graph (i -> f(i)), or finding the middle.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head
while slow is not fast: # both move 1 step now
slow, fast = slow.next, fast.next
return slow
return None
def middle_node(head): # second middle for even length
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow
def find_duplicate(nums): # values 1..n, array as a function
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow, fast = nums[slow], nums[fast]
return slow
def is_happy(n):
def nxt(x):
return sum(int(d) ** 2 for d in str(x))
slow, fast = n, nxt(n)
while fast != 1 and slow != fast:
slow = nxt(slow)
fast = nxt(nxt(fast))
return fast == 1
Problems: Linked List Cycle I/II, Middle of the Linked List, Happy Number, Find the Duplicate Number, Palindrome Linked List, Reorder List.
12. Linked Lists
def reverse_list(head):
prev, cur = None, head
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
def reverse_between(head, left, right): # 1-indexed
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
cur = prev.next
for _ in range(right - left): # head-insertion
nxt = cur.next
cur.next = nxt.next
nxt.next = prev.next
prev.next = nxt
return dummy.next
def reverse_k_group(head, k):
def length(node):
n = 0
while node:
n += 1
node = node.next
return n
dummy = ListNode(0, head)
prev, remaining = dummy, length(head)
while remaining >= k:
cur = prev.next
nxt = cur.next
for _ in range(k - 1):
cur.next = nxt.next
nxt.next = prev.next
prev.next = nxt
nxt = cur.next
prev = cur
remaining -= k
return dummy.next
def merge_two_sorted(a, b):
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
slow.next = slow.next.next
return dummy.next
def sort_list(head): # merge sort, O(n log n) / O(log n)
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
mid, slow.next = slow.next, None
return merge_two_sorted(sort_list(head), sort_list(mid))
Key habits: use a dummy head whenever the first node can change; draw the pointers before writing; count nodes if you need positional logic.
Problems: Reverse Linked List I/II, Reverse Nodes in k-Group, Merge Two/K Sorted Lists, Remove Nth From End, Copy List with Random Pointer, Add Two Numbers, LRU Cache, Flatten Multilevel List.
13. Trees — DFS
Use when: path-based questions, subtree aggregates, or anything naturally recursive. Decide what each call returns upward vs. what it passes downward.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# Pass state DOWN: root-to-leaf sum
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right:
return target == root.val
rest = target - root.val
return has_path_sum(root.left, rest) or has_path_sum(root.right, rest)
# Collect all root-to-leaf paths (backtracking on a tree)
def all_paths(root):
out, path = [], []
def dfs(node):
if not node:
return
path.append(node.val)
if not node.left and not node.right:
out.append(path[:])
else:
dfs(node.left)
dfs(node.right)
path.pop()
dfs(root)
return out
# Return UP + track a global: diameter
def diameter(root):
best = 0
def depth(node):
nonlocal best
if not node:
return 0
l, r = depth(node.left), depth(node.right)
best = max(best, l + r) # edges through this node
return 1 + max(l, r)
depth(root)
return best
# Max path sum (values may be negative)
def max_path_sum(root):
best = float('-inf')
def gain(node):
nonlocal best
if not node:
return 0
l = max(gain(node.left), 0) # drop negative branches
r = max(gain(node.right), 0)
best = max(best, node.val + l + r)
return node.val + max(l, r)
gain(root)
return best
# Lowest common ancestor (general binary tree)
def lca(root, p, q):
if not root or root is p or root is q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root
return left or right
# Iterative inorder (know this one — recursion isn't always allowed)
def inorder_iterative(root):
out, stack, cur = [], [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return out
# Build tree from preorder + inorder
def build_tree(preorder, inorder):
index = {v: i for i, v in enumerate(inorder)}
self_pos = [0]
def helper(lo, hi):
if lo > hi:
return None
val = preorder[self_pos[0]]
self_pos[0] += 1
node = TreeNode(val)
mid = index[val]
node.left = helper(lo, mid - 1)
node.right = helper(mid + 1, hi)
return node
return helper(0, len(inorder) - 1)
# Serialize / deserialize (preorder with null markers)
def serialize(root):
out = []
def dfs(node):
if not node:
out.append('#')
return
out.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ','.join(out)
def deserialize(data):
it = iter(data.split(','))
def dfs():
tok = next(it)
if tok == '#':
return None
node = TreeNode(int(tok))
node.left = dfs()
node.right = dfs()
return node
return dfs()
Problems: Maximum Depth, Balanced Binary Tree, Diameter, Path Sum I/II/III, Binary Tree Maximum Path Sum, LCA, Invert Tree, Same Tree, Subtree of Another Tree, Serialize/Deserialize, Flatten to Linked List, House Robber III.
14. Trees — BFS
Use when: level-by-level output, shortest depth, or "right side / widest level" questions.
from collections import deque
def level_order(root):
if not root:
return []
out, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # snapshot the level size
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(level)
return out
def zigzag_level_order(root):
if not root:
return []
out, q, ltr = [], deque([root]), True
while q:
level = deque()
for _ in range(len(q)):
node = q.popleft()
if ltr:
level.append(node.val)
else:
level.appendleft(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
out.append(list(level))
ltr = not ltr
return out
def right_side_view(root):
if not root:
return []
out, q = [], deque([root])
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
out.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return out
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, d = q.popleft()
if not node.left and not node.right:
return d
if node.left:
q.append((node.left, d + 1))
if node.right:
q.append((node.right, d + 1))
return 0
Problems: Level Order Traversal I/II, Zigzag, Right Side View, Average of Levels, Minimum Depth, Connect Level Order Siblings, Populating Next Right Pointers, Vertical Order Traversal, All Nodes Distance K.
15. Binary Search Trees
Key fact: inorder traversal of a BST is sorted. Most BST problems reduce to that or to pruning one subtree.
def bst_search(root, target):
while root and root.val != target:
root = root.left if target < root.val else root.right
return root
def bst_insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return root
def bst_delete(root, key):
if not root:
return None
if key < root.val:
root.left = bst_delete(root.left, key)
elif key > root.val:
root.right = bst_delete(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
succ = root.right # smallest in right subtree
while succ.left:
succ = succ.left
root.val = succ.val
root.right = bst_delete(root.right, succ.val)
return root
def is_valid_bst(root):
def check(node, lo, hi):
if not node:
return True
if not (lo < node.val < hi):
return False
return check(node.left, lo, node.val) and check(node.right, node.val, hi)
return check(root, float('-inf'), float('inf'))
def kth_smallest(root, k):
stack, cur = [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right
return -1
def lca_bst(root, p, q):
while root:
if p.val < root.val > q.val:
root = root.left
elif p.val > root.val < q.val:
root = root.right
else:
return root
return None
def sorted_array_to_bst(nums):
def build(lo, hi):
if lo > hi:
return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(nums) - 1)
Problems: Validate BST, Kth Smallest, Insert/Delete/Search in BST, LCA of BST, Convert Sorted Array to BST, Range Sum of BST, Recover BST, Inorder Successor.
16. Trie
Use when: prefix queries, dictionary lookups during a grid/DFS search, XOR-maximization over bits.
class TrieNode:
__slots__ = ('children', 'is_word')
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
def _find(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def search(self, word):
node = self._find(word)
return bool(node and node.is_word)
def starts_with(self, prefix):
return self._find(prefix) is not None
def search_wildcard(self, word): # '.' matches any character
def dfs(node, i):
if i == len(word):
return node.is_word
ch = word[i]
if ch == '.':
return any(dfs(child, i + 1) for child in node.children.values())
return ch in node.children and dfs(node.children[ch], i + 1)
return dfs(self.root, 0)
# Binary trie for maximum XOR pair
def max_xor_pair(nums, bits=32):
root = {}
for x in nums:
node = root
for b in range(bits - 1, -1, -1):
bit = (x >> b) & 1
node = node.setdefault(bit, {})
best = 0
for x in nums:
node, cur = root, 0
for b in range(bits - 1, -1, -1):
bit = (x >> b) & 1
want = 1 - bit
if want in node:
cur |= 1 << b
node = node[want]
else:
node = node[bit]
best = max(best, cur)
return best
Complexity: insert/search O(L); memory O(total characters). Problems: Implement Trie, Add and Search Word, Word Search II, Longest Common Prefix, Replace Words, Maximum XOR of Two Numbers, Design Search Autocomplete.
17. Heaps / Top-K / Two Heaps
Use when: you need the k best without a full sort, streaming data, or a running median.
import heapq
# heapq is a MIN-heap. For a max-heap, push negatives.
def k_largest(nums, k):
return heapq.nlargest(k, nums) # O(n log k)
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for v in nums[k:]:
if v > heap[0]:
heapq.heapreplace(heap, v)
return heap[0]
def top_k_frequent(nums, k):
counts = Counter(nums)
return [v for v, _ in counts.most_common(k)]
def k_closest_to_origin(points, k):
return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)
def merge_k_sorted_lists(lists): # lists of ListNode
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# Two heaps: running median
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (negated), lower half
self.large = [] # min-heap, upper half
def add(self, num):
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
# Scheduling with a heap: task scheduler / reorganize string
def reorganize_string(s):
heap = [(-c, ch) for ch, c in Counter(s).items()]
heapq.heapify(heap)
out, prev = [], None
while heap:
cnt, ch = heapq.heappop(heap)
out.append(ch)
if prev:
heapq.heappush(heap, prev)
prev = (cnt + 1, ch) if cnt + 1 else None
return "".join(out) if len(out) == len(s) else ""
Complexity: push/pop O(log n); building via heapify O(n).
Problems: Kth Largest Element, Top K Frequent, K Closest Points, Merge K Sorted Lists, Find Median from Data Stream, Task Scheduler, Reorganize String, Sliding Window Median, IPO, Meeting Rooms II, Ugly Number II.
18. Graphs — Traversal
from collections import defaultdict, deque
def build_graph(n, edges, directed=False):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
if not directed:
g[v].append(u)
return g
def dfs_iterative(g, start):
seen, stack, order = {start}, [start], []
while stack:
node = stack.pop()
order.append(node)
for nxt in g[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return order
def bfs_shortest_unweighted(g, start, goal):
if start == goal:
return 0
seen, q = {start}, deque([(start, 0)])
while q:
node, d = q.popleft()
for nxt in g[node]:
if nxt == goal:
return d + 1
if nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
return -1
def connected_components(n, edges):
g = build_graph(n, edges)
seen, count = set(), 0
for s in range(n):
if s in seen:
continue
count += 1
stack = [s]
seen.add(s)
while stack:
node = stack.pop()
for nxt in g[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return count
# Grid DFS: count islands (flood fill, mutate to mark visited)
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
def sink(r, c):
stack = [(r, c)]
while stack:
i, j = stack.pop()
if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
grid[i][j] = '0'
stack.extend([(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)])
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == '1':
count += 1
sink(r, c)
return count
# Multi-source BFS: rotting oranges / nearest 0
def rotting_oranges(grid):
m, n = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
minutes += 1
for _ in range(len(q)):
r, c = q.popleft()
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
return -1 if fresh else minutes
# Bipartite check (2-coloring)
def is_bipartite(graph):
color = {}
for s in range(len(graph)):
if s in color:
continue
color[s] = 0
q = deque([s])
while q:
node = q.popleft()
for nxt in graph[node]:
if nxt not in color:
color[nxt] = color[node] ^ 1
q.append(nxt)
elif color[nxt] == color[node]:
return False
return True
# Cycle detection in a directed graph (3-color DFS)
def has_cycle_directed(n, g):
WHITE, GRAY, BLACK = 0, 1, 2
state = [WHITE] * n
def dfs(u):
state[u] = GRAY
for v in g[u]:
if state[v] == GRAY:
return True
if state[v] == WHITE and dfs(v):
return True
state[u] = BLACK
return False
return any(state[u] == WHITE and dfs(u) for u in range(n))
Complexity: O(V + E). Problems: Number of Islands, Clone Graph, Word Ladder, Rotting Oranges, Pacific Atlantic Water Flow, Surrounded Regions, Course Schedule, Is Graph Bipartite, Walls and Gates, 01 Matrix, Open the Lock.
Grid BFS vs DFS: shortest path → BFS. Reachability/area/flood fill → either, DFS is shorter. Beware Python's recursion limit on large grids; prefer iterative.
19. Topological Sort
Use when: ordering with prerequisites; also detects cycles in a DAG candidate.
def topological_sort(n, prerequisites):
"""prerequisites: [a, b] means b must come before a."""
g = defaultdict(list)
indeg = [0] * n
for a, b in prerequisites:
g[b].append(a)
indeg[a] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in g[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return order if len(order) == n else [] # empty -> cycle
# DFS variant (reverse postorder)
def topo_dfs(n, g):
state = [0] * n
order = []
def dfs(u):
state[u] = 1
for v in g[u]:
if state[v] == 1:
return False
if state[v] == 0 and not dfs(v):
return False
state[u] = 2
order.append(u)
return True
for u in range(n):
if state[u] == 0 and not dfs(u):
return []
return order[::-1]
# Longest path in a DAG / DP over topological order
def longest_path_dag(n, edges):
g = defaultdict(list)
indeg = [0] * n
for u, v, w in edges:
g[u].append((v, w))
indeg[v] += 1
dist = [0] * n
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
u = q.popleft()
for v, w in g[u]:
dist[v] = max(dist[v], dist[u] + w)
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return max(dist)
Problems: Course Schedule I/II, Alien Dictionary, Minimum Height Trees, Sequence Reconstruction, Parallel Courses, Sort Items by Groups.
20. Union-Find (DSU)
Use when: dynamic connectivity, "count groups," Kruskal's MST, or detecting cycles in an undirected graph.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # number of components
def find(self, x):
while self.parent[x] != x: # path halving
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected -> cycle edge
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
self.count -= 1
return True
def connected(self, a, b):
return self.find(a) == self.find(b)
# Non-integer nodes: dict-backed DSU
class DSUDict:
def __init__(self):
self.parent = {}
def find(self, x):
self.parent.setdefault(x, x)
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra != rb:
self.parent[rb] = ra
Complexity: near O(1) amortized (inverse Ackermann). Problems: Number of Provinces, Redundant Connection, Accounts Merge, Number of Islands II, Satisfiability of Equality Equations, Most Stones Removed, Longest Consecutive Sequence (union variant), Kruskal MST.
21. Shortest Paths
import heapq
# Dijkstra: non-negative weights, O(E log V)
def dijkstra(n, graph, src):
"""graph: {u: [(v, w), ...]}"""
dist = [float('inf')] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
# Bellman-Ford: handles negative weights, detects negative cycles, O(V*E)
def bellman_ford(n, edges, src):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
changed = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed:
break
for u, v, w in edges: # extra pass
if dist[u] + w < dist[v]:
return None # negative cycle
return dist
# Bellman-Ford with at most k edges (cheapest flight within k stops)
def cheapest_k_stops(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1):
nxt = dist[:] # copy = "at most one more edge"
for u, v, w in flights:
if dist[u] + w < nxt[v]:
nxt[v] = dist[u] + w
dist = nxt
return -1 if dist[dst] == float('inf') else dist[dst]
# Floyd-Warshall: all pairs, O(V^3)
def floyd_warshall(n, edges):
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w)
for k in range(n):
for i in range(n):
dik = dist[i][k]
if dik == float('inf'):
continue
for j in range(n):
if dik + dist[k][j] < dist[i][j]:
dist[i][j] = dik + dist[k][j]
return dist
# 0-1 BFS: weights are only 0 or 1, O(V + E)
def zero_one_bfs(n, graph, src):
dist = [float('inf')] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
Which one: unweighted → BFS. Weights 0/1 → 0-1 BFS. Non-negative → Dijkstra. Negatives or edge-count limits → Bellman-Ford. All pairs, small V → Floyd-Warshall. Minimize the maximum edge on a path → Dijkstra with max instead of +, or binary search + BFS.
Problems: Network Delay Time, Cheapest Flights Within K Stops, Path with Minimum Effort, Swim in Rising Water, Path with Maximum Probability, Find the City With the Smallest Number of Neighbors.
22. Minimum Spanning Tree
def kruskal(n, edges):
"""edges: [(w, u, v)] -> (total_weight, chosen_edges)"""
edges.sort()
dsu = DSU(n)
total, chosen = 0, []
for w, u, v in edges:
if dsu.union(u, v):
total += w
chosen.append((u, v, w))
if len(chosen) == n - 1:
break
return total, chosen
def prim(n, graph):
"""graph: {u: [(v, w)]}"""
seen = [False] * n
pq = [(0, 0)]
total = 0
while pq:
w, u = heapq.heappop(pq)
if seen[u]:
continue
seen[u] = True
total += w
for v, wt in graph[u]:
if not seen[v]:
heapq.heappush(pq, (wt, v))
return total if all(seen) else -1
Problems: Min Cost to Connect All Points, Connecting Cities With Minimum Cost, Optimize Water Distribution.
23. Backtracking
Use when: enumerate all subsets / permutations / combinations / board configurations. The shape is always: choose → explore → un-choose.
# Subsets (power set)
def subsets(nums):
out, path = [], []
def dfs(start):
out.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
# Subsets with duplicates: sort, then skip repeats at the same depth
def subsets_with_dup(nums):
nums.sort()
out, path = [], []
def dfs(start):
out.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return out
# Permutations
def permutations(nums):
out, used, path = [], [False] * len(nums), []
def dfs():
if len(path) == len(nums):
out.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
dfs()
path.pop()
used[i] = False
dfs()
return out
# Permutations with duplicates
def permute_unique(nums):
nums.sort()
out, used, path = [], [False] * len(nums), []
def dfs():
if len(path) == len(nums):
out.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue # dedupe at this level
used[i] = True
path.append(nums[i])
dfs()
path.pop()
used[i] = False
dfs()
return out
# Combination sum (unlimited reuse)
def combination_sum(candidates, target):
candidates.sort()
out, path = [], []
def dfs(start, remain):
if remain == 0:
out.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
break # pruning via sort
path.append(candidates[i])
dfs(i, remain - candidates[i]) # i, not i+1 -> reuse allowed
path.pop()
dfs(0, target)
return out
# Palindrome partitioning
def partition_palindromes(s):
out, path = [], []
def dfs(start):
if start == len(s):
out.append(path[:])
return
for end in range(start + 1, len(s) + 1):
piece = s[start:end]
if piece == piece[::-1]:
path.append(piece)
dfs(end)
path.pop()
dfs(0)
return out
# N-Queens with O(1) conflict checks
def solve_n_queens(n):
out, cols, diag, anti, board = [], set(), set(), set(), []
def dfs(r):
if r == n:
out.append(board[:])
return
for c in range(n):
if c in cols or (r - c) in diag or (r + c) in anti:
continue
cols.add(c); diag.add(r - c); anti.add(r + c)
board.append('.' * c + 'Q' + '.' * (n - c - 1))
dfs(r + 1)
board.pop()
cols.remove(c); diag.remove(r - c); anti.remove(r + c)
dfs(0)
return out
# Grid backtracking: word search
def word_search(board, word):
m, n = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[i]:
return False
board[r][c] = '#' # mark visited
found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
board[r][c] = word[i] # restore
return found
return any(dfs(r, c, 0) for r in range(m) for c in range(n))
# Sudoku solver (constraint sets + return True to stop early)
def solve_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
v = board[r][c]
if v == '.':
empties.append((r, c))
else:
rows[r].add(v); cols[c].add(v); boxes[(r // 3) * 3 + c // 3].add(v)
def dfs(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in '123456789':
if d in rows[r] or d in cols[c] or d in boxes[b]:
continue
board[r][c] = d
rows[r].add(d); cols[c].add(d); boxes[b].add(d)
if dfs(k + 1):
return True
board[r][c] = '.'
rows[r].remove(d); cols[c].remove(d); boxes[b].remove(d)
return False
dfs(0)
return board
Pruning checklist: sort input to enable early break; keep running sums instead of recomputing; use sets for O(1) conflict checks; return early once one solution suffices; memoize when subproblems repeat (then it's DP).
Problems: Subsets I/II, Permutations I/II, Combination Sum I–IV, Palindrome Partitioning, N-Queens, Word Search I/II, Sudoku Solver, Letter Combinations of a Phone Number, Generate Parentheses, Restore IP Addresses, Word Break II.
24. Dynamic Programming
Use when: overlapping subproblems + optimal substructure. Define the state precisely first — the recurrence usually falls out.
Workflow: brute-force recursion → memoize (top-down) → convert to tabulation (bottom-up) → compress space.
from functools import lru_cache
# --- 1-D: climbing stairs / Fibonacci with O(1) space ---
def climb_stairs(n):
a, b = 1, 1
for _ in range(n - 1):
a, b = b, a + b
return b
# --- House robber (skip-adjacent) ---
def rob(nums):
take, skip = 0, 0
for v in nums:
take, skip = skip + v, max(skip, take)
return max(take, skip)
# --- Kadane: maximum subarray ---
def max_subarray(nums):
best = cur = nums[0]
for v in nums[1:]:
cur = max(v, cur + v)
best = max(best, cur)
return best
# --- 0/1 Knapsack: each item once ---
def knapsack_01(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w - 1, -1): # DESCENDING -> each item once
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
# --- Unbounded knapsack / coin change (min coins) ---
def coin_change(coins, amount):
dp = [0] + [float('inf')] * amount
for c in coins:
for a in range(c, amount + 1): # ASCENDING -> unlimited reuse
dp[a] = min(dp[a], dp[a - c] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]
# --- Count combinations (order doesn't matter) ---
def coin_change_ways(coins, amount):
dp = [1] + [0] * amount
for c in coins: # coins OUTSIDE -> combinations
for a in range(c, amount + 1):
dp[a] += dp[a - c]
return dp[amount]
# --- Count permutations (order matters) ---
def combination_sum_iv(nums, target):
dp = [1] + [0] * target
for t in range(1, target + 1): # target OUTSIDE -> permutations
for v in nums:
if v <= t:
dp[t] += dp[t - v]
return dp[target]
# --- Partition into equal subsets (subset-sum feasibility) ---
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = 1 # bitset: bit i = sum i reachable
for v in nums:
dp |= dp << v
return bool(dp >> target & 1)
# --- LCS: two-sequence grid DP ---
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# --- Edit distance ---
def edit_distance(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1))
for i in range(1, m + 1):
cur = [i] + [0] * n
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])
prev = cur
return prev[n]
# --- LIS in O(n log n) ---
import bisect
def length_of_lis(nums):
tails = []
for v in nums:
i = bisect.bisect_left(tails, v) # bisect_right -> non-decreasing
if i == len(tails):
tails.append(v)
else:
tails[i] = v
return len(tails)
# --- Grid paths with obstacles ---
def unique_paths_with_obstacles(grid):
n = len(grid[0])
dp = [0] * n
dp[0] = 1
for row in grid:
for j in range(n):
if row[j] == 1:
dp[j] = 0
elif j > 0:
dp[j] += dp[j - 1]
return dp[-1]
# --- Interval DP: burst balloons ---
def max_coins(nums):
a = [1] + nums + [1]
n = len(a)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for lo in range(n - length):
hi = lo + length
for k in range(lo + 1, hi): # k is burst LAST
dp[lo][hi] = max(dp[lo][hi],
dp[lo][k] + dp[k][hi] + a[lo] * a[k] * a[hi])
return dp[0][n - 1]
# --- Palindromic substrings via expand-around-center ---
def count_palindromic_substrings(s):
total = 0
for center in range(len(s)):
for lo, hi in ((center, center), (center, center + 1)):
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
total += 1
lo -= 1
hi += 1
return total
# --- Bitmask DP: travelling salesman, n <= ~20 ---
def tsp(dist):
n = len(dist)
FULL = (1 << n) - 1
@lru_cache(maxsize=None)
def go(at, mask):
if mask == FULL:
return dist[at][0]
best = float('inf')
for nxt in range(n):
if mask >> nxt & 1:
continue
best = min(best, dist[at][nxt] + go(nxt, mask | 1 << nxt))
return best
return go(0, 1)
# --- Tree DP: house robber III ---
def rob_tree(root):
def dfs(node):
if not node:
return (0, 0) # (rob this, skip this)
l = dfs(node.left)
r = dfs(node.right)
return (node.val + l[1] + r[1], max(l) + max(r))
return max(dfs(root))
# --- State machine DP: stock with cooldown / k transactions ---
def max_profit_with_cooldown(prices):
hold, sold, rest = float('-inf'), 0, 0
for p in prices:
hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
return max(sold, rest)
# --- Digit DP skeleton: count numbers <= N with a property ---
def count_numbers_without_consecutive_ones(n):
s = bin(n)[2:]
@lru_cache(maxsize=None)
def go(i, prev_one, tight):
if i == len(s):
return 1
limit = int(s[i]) if tight else 1
total = 0
for d in range(limit + 1):
if prev_one and d == 1:
continue
total += go(i + 1, d == 1, tight and d == limit)
return total
return go(0, False, True)
Common state definitions
| Problem family | State |
|---|---|
| Subsequence of one array | dp[i] = answer for prefix ending at i |
| Two strings/arrays | dp[i][j] = answer for prefixes i, j |
| Knapsack | dp[i][c] = best using first i items, capacity c |
| Intervals / merging | dp[i][j] = best for segment [i, j] |
| Subsets of small n | dp[mask] or dp[at][mask] |
| Buy/sell, states with rules | dp[i][state] |
| Trees | return a tuple per node (include / exclude) |
| Digits of a number | dp[pos][carried state][tight] |
Space compression: if dp[i] only reads dp[i-1], keep two rows (or one, iterating in the right direction). Descending inner loop = each item once; ascending = reuse allowed.
Problems: Climbing Stairs, House Robber I/II/III, Coin Change I/II, Partition Equal Subset Sum, Target Sum, Longest Common Subsequence, Edit Distance, Longest Increasing Subsequence, Word Break, Decode Ways, Unique Paths, Minimum Path Sum, Best Time to Buy and Sell Stock I–IV, Burst Balloons, Regular Expression Matching, Wildcard Matching, Longest Palindromic Subsequence, Distinct Subsequences, Cherry Pickup, Stone Game.
25. Greedy
Use when: a locally optimal choice is provably globally optimal. Test by finding an exchange argument — swapping any other choice for the greedy one never hurts.
# Activity selection: earliest finishing time first
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, float('-inf')
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
# Jump Game II: BFS-like greedy over reachable ranges
def min_jumps(nums):
jumps = cur_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumps
# Gas station: unique start if total >= 0
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start = tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start, tank = i + 1, 0
return start
# Partition labels: extend to the last occurrence
def partition_labels(s):
last = {ch: i for i, ch in enumerate(s)}
out, start, end = [], 0, 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
out.append(end - start + 1)
start = i + 1
return out
# Minimum arrows / minimum removals: sort by end
def find_min_arrows(points):
points.sort(key=lambda x: x[1])
arrows, end = 0, float('-inf')
for s, e in points:
if s > end:
arrows += 1
end = e
return arrows
# Huffman-style merging: always combine the two cheapest
def min_cost_to_connect_sticks(sticks):
heapq.heapify(sticks)
total = 0
while len(sticks) > 1:
a = heapq.heappop(sticks)
b = heapq.heappop(sticks)
total += a + b
heapq.heappush(sticks, a + b)
return total
Problems: Jump Game I/II, Gas Station, Task Scheduler, Partition Labels, Non-overlapping Intervals, Minimum Number of Arrows, Candy, Queue Reconstruction by Height, Boats to Save People, Two City Scheduling.
26. Bit Manipulation
# Essentials
x & 1 # odd?
x >> 1 # divide by 2
x & (x - 1) # clear lowest set bit
x & -x # isolate lowest set bit
x | (x + 1) # set lowest zero bit
bin(x).count('1') # popcount
x.bit_length() # position of highest set bit
x ^ y # differing bits
1 << k # 2**k
x & ~(1 << k) # clear bit k
x ^ (1 << k) # toggle bit k
(x >> k) & 1 # read bit k
x & (x - 1) == 0 # power of two (x > 0)
def single_number(nums): # everyone twice except one
res = 0
for v in nums:
res ^= v
return res
def single_number_two_uniques(nums): # exactly two appear once
xor_all = 0
for v in nums:
xor_all ^= v
bit = xor_all & -xor_all # a differing bit
a = b = 0
for v in nums:
if v & bit:
a ^= v
else:
b ^= v
return [a, b]
def single_number_three_times(nums): # everyone 3x except one
ones = twos = 0
for v in nums:
ones = (ones ^ v) & ~twos
twos = (twos ^ v) & ~ones
return ones
def subsets_bitmask(nums):
n = len(nums)
return [[nums[i] for i in range(n) if mask >> i & 1]
for mask in range(1 << n)]
def iterate_submasks(mask): # all submasks of mask
sub = mask
while sub:
yield sub
sub = (sub - 1) & mask
yield 0
def counting_bits(n): # popcount for 0..n
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp
def add_without_plus(a, b, bits=32):
mask = (1 << bits) - 1
while b & mask:
carry = (a & b) << 1
a = a ^ b
b = carry
return a & mask if b > mask else a
Problems: Single Number I/II/III, Number of 1 Bits, Counting Bits, Reverse Bits, Missing Number, Subsets, Sum of Two Integers, Bitwise AND of Numbers Range, Maximum XOR, Minimum Number of K Consecutive Bit Flips.
27. Math & Number Theory
import math
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
# math.gcd / math.lcm exist in the standard library
def sieve(n):
is_prime = bytearray([1]) * (n + 1)
is_prime[0:2] = b'\x00\x00'
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
is_prime[i * i::i] = bytearray(len(is_prime[i * i::i]))
return [i for i in range(n + 1) if is_prime[i]]
def prime_factors(n):
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
def divisors(n):
small, large = [], []
d = 1
while d * d <= n:
if n % d == 0:
small.append(d)
if d != n // d:
large.append(n // d)
d += 1
return small + large[::-1]
MOD = 10 ** 9 + 7
def power_mod(base, exp, mod=MOD):
result = 1
base %= mod
while exp:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
# Built-in: pow(base, exp, mod) — use this in interviews
def mod_inverse(a, mod=MOD): # mod must be prime
return pow(a, mod - 2, mod)
def n_choose_k(n, k, mod=MOD):
if k < 0 or k > n:
return 0
num = den = 1
for i in range(k):
num = num * (n - i) % mod
den = den * (i + 1) % mod
return num * mod_inverse(den, mod) % mod
# Small values: math.comb(n, k)
def digits_sum(n):
total = 0
while n:
total += n % 10
n //= 10
return total
def reverse_integer(n):
sign = -1 if n < 0 else 1
rev, n = 0, abs(n)
while n:
rev = rev * 10 + n % 10
n //= 10
return sign * rev
Problems: Count Primes, Happy Number, Power of Three, Excel Sheet Column Number, Pow(x, n), Sqrt(x), Fraction to Recurring Decimal, Ugly Number, Rotate Function, Random Point in Circle.
28. Fenwick Tree & Segment Tree
Use when: interleaved range queries and point updates (Fenwick), or range queries with range updates / arbitrary associative merges (segment tree).
class Fenwick:
"""1-indexed prefix sums; point update, prefix query. O(log n) each."""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta): # i is 1-based
while i <= self.n:
self.tree[i] += delta
i += i & -i
def prefix(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total
def range_sum(self, l, r): # inclusive, 1-based
return self.prefix(r) - self.prefix(l - 1)
class SegmentTree:
"""Iterative, range query + point update. Swap `merge` for min/max/gcd."""
def __init__(self, data, merge=lambda a, b: a + b, identity=0):
self.n = len(data)
self.merge = merge
self.identity = identity
self.tree = [identity] * (2 * self.n)
self.tree[self.n:] = data
for i in range(self.n - 1, 0, -1):
self.tree[i] = merge(self.tree[2 * i], self.tree[2 * i + 1])
def update(self, i, value):
i += self.n
self.tree[i] = value
i //= 2
while i:
self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])
i //= 2
def query(self, l, r): # [l, r)
res_left = res_right = self.identity
l += self.n
r += self.n
while l < r:
if l & 1:
res_left = self.merge(res_left, self.tree[l])
l += 1
if r & 1:
r -= 1
res_right = self.merge(self.tree[r], res_right)
l //= 2
r //= 2
return self.merge(res_left, res_right)
class LazySegmentTree:
"""Range add + range sum, recursive with lazy propagation."""
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _push(self, node, lo, hi):
if self.lazy[node]:
self.tree[node] += self.lazy[node] * (hi - lo + 1)
if lo != hi:
self.lazy[2 * node] += self.lazy[node]
self.lazy[2 * node + 1] += self.lazy[node]
self.lazy[node] = 0
def update(self, l, r, val, node=1, lo=0, hi=None):
if hi is None:
hi = self.n - 1
self._push(node, lo, hi)
if r < lo or hi < l:
return
if l <= lo and hi <= r:
self.lazy[node] += val
self._push(node, lo, hi)
return
mid = (lo + hi) // 2
self.update(l, r, val, 2 * node, lo, mid)
self.update(l, r, val, 2 * node + 1, mid + 1, hi)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, l, r, node=1, lo=0, hi=None):
if hi is None:
hi = self.n - 1
self._push(node, lo, hi)
if r < lo or hi < l:
return 0
if l <= lo and hi <= r:
return self.tree[node]
mid = (lo + hi) // 2
return (self.query(l, r, 2 * node, lo, mid)
+ self.query(l, r, 2 * node + 1, mid + 1, hi))
# Classic Fenwick application: count inversions
def count_inversions(nums):
ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}
bit = Fenwick(len(ranks))
inversions = 0
for v in reversed(nums):
inversions += bit.prefix(ranks[v] - 1) # already-seen smaller values
bit.update(ranks[v], 1)
return inversions
Problems: Range Sum Query — Mutable, Count of Smaller Numbers After Self, Reverse Pairs, Range Sum Query 2D, My Calendar III, Falling Squares, Number of Longest Increasing Subsequence.
29. String Algorithms
# KMP prefix function (longest proper prefix that is also a suffix)
def build_lps(pattern):
lps = [0] * len(pattern)
k = 0
for i in range(1, len(pattern)):
while k and pattern[i] != pattern[k]:
k = lps[k - 1]
if pattern[i] == pattern[k]:
k += 1
lps[i] = k
return lps
def kmp_search(text, pattern):
if not pattern:
return 0
lps = build_lps(pattern)
k = 0
for i, ch in enumerate(text):
while k and ch != pattern[k]:
k = lps[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
return i - k + 1
return -1
# Rabin-Karp rolling hash
def rabin_karp(text, pattern, base=256, mod=(1 << 61) - 1):
n, m = len(text), len(pattern)
if m > n:
return -1
high = pow(base, m - 1, mod)
target = 0
window = 0
for i in range(m):
target = (target * base + ord(pattern[i])) % mod
window = (window * base + ord(text[i])) % mod
for i in range(n - m + 1):
if window == target and text[i:i + m] == pattern:
return i
if i + m < n:
window = ((window - ord(text[i]) * high) * base
+ ord(text[i + m])) % mod
return -1
# Longest palindromic substring: expand around centers, O(n^2)
def longest_palindrome(s):
best = ""
for i in range(len(s)):
for lo, hi in ((i, i), (i, i + 1)):
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo -= 1
hi += 1
if hi - lo - 1 > len(best):
best = s[lo + 1:hi]
return best
# Anagram grouping / comparison
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups[tuple(sorted(w))].append(w)
return list(groups.values())
def is_anagram(a, b):
return Counter(a) == Counter(b)
# Encode / decode strings with length prefixes (safe delimiter-free protocol)
def encode(strs):
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(data):
out, i = [], 0
while i < len(data):
j = data.index('#', i)
length = int(data[i:j])
out.append(data[j + 1:j + 1 + length])
i = j + 1 + length
return out
# Z-function (all prefix-match lengths) — pattern matching, distinct substrings
def z_function(s):
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z
Problems: Implement strStr, Repeated Substring Pattern, Shortest Palindrome, Longest Palindromic Substring, Group Anagrams, Valid Anagram, Encode and Decode Strings, Longest Happy Prefix, Distinct Subsequences.
30. Design Problems
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False)
class MinStack:
def __init__(self):
self.stack = [] # (value, min_so_far)
def push(self, x):
cur_min = x if not self.stack else min(x, self.stack[-1][1])
self.stack.append((x, cur_min))
def pop(self):
return self.stack.pop()[0]
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]
class QueueViaStacks:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, x):
self.inbox.append(x)
def _shift(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._shift()
return self.outbox.pop()
def peek(self):
self._shift()
return self.outbox[-1]
class HitCounter:
"""Hits in the last 300 seconds."""
def __init__(self):
self.q = deque()
def hit(self, timestamp):
self.q.append(timestamp)
def get_hits(self, timestamp):
while self.q and self.q[0] <= timestamp - 300:
self.q.popleft()
return len(self.q)
class RandomizedSet:
"""O(1) insert / remove / getRandom."""
def __init__(self):
self.items = []
self.index = {}
def insert(self, val):
if val in self.index:
return False
self.index[val] = len(self.items)
self.items.append(val)
return True
def remove(self, val):
if val not in self.index:
return False
i = self.index.pop(val)
last = self.items.pop()
if i < len(self.items):
self.items[i] = last
self.index[last] = i
return True
def get_random(self):
import random
return random.choice(self.items)
Problems: LRU Cache, LFU Cache, Min Stack, Implement Queue using Stacks, Design HashMap, Design Twitter, Insert Delete GetRandom O(1), Time Based Key-Value Store, Design Hit Counter, Snapshot Array, Tic-Tac-Toe.
31. Selection & Sampling
import random
# Quickselect: kth smallest in expected O(n)
def quickselect(nums, k): # k is 1-indexed
nums = nums[:]
lo, hi = 0, len(nums) - 1
target = k - 1
while True:
pivot = nums[random.randint(lo, hi)]
left, mid, right = [], [], []
for v in nums[lo:hi + 1]:
(left if v < pivot else mid if v == pivot else right).append(v)
if target < lo + len(left):
nums[lo:hi + 1] = left + mid + right
hi = lo + len(left) - 1
elif target < lo + len(left) + len(mid):
return pivot
else:
nums[lo:hi + 1] = left + mid + right
lo = lo + len(left) + len(mid)
# Dutch national flag: 3-way partition in one pass
def sort_colors(nums):
lo, i, hi = 0, 0, len(nums) - 1
while i <= hi:
if nums[i] == 0:
nums[lo], nums[i] = nums[i], nums[lo]
lo += 1
i += 1
elif nums[i] == 2:
nums[hi], nums[i] = nums[i], nums[hi]
hi -= 1
else:
i += 1
return nums
# Reservoir sampling: pick k from a stream of unknown length
def reservoir_sample(stream, k):
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
# Fisher-Yates shuffle
def shuffle(nums):
for i in range(len(nums) - 1, 0, -1):
j = random.randint(0, i)
nums[i], nums[j] = nums[j], nums[i]
return nums
# Weighted random pick via prefix sums + binary search
class WeightedRandom:
def __init__(self, weights):
self.prefix = []
total = 0
for w in weights:
total += w
self.prefix.append(total)
self.total = total
def pick(self):
target = random.random() * self.total
return bisect.bisect_right(self.prefix, target)
# Merge sort (stable, and the base for counting inversions)
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
Problems: Kth Largest Element, Sort Colors, Top K Frequent, Shuffle an Array, Random Pick with Weight, Linked List Random Node, Count of Smaller Numbers After Self, Reverse Pairs.
32. Python toolkit for interviews
# Imports worth typing on sight
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache, cache, cmp_to_key
from itertools import accumulate, permutations, combinations, product, pairwise
import heapq, bisect, math, random
# Counters
c = Counter("mississippi")
c.most_common(2) # [('i', 4), ('s', 4)]
Counter("abc") - Counter("ab") # multiset subtraction
# defaultdict avoids key checks
graph = defaultdict(list)
graph[1].append(2)
# deque = O(1) both ends
dq = deque([1, 2, 3])
dq.appendleft(0); dq.pop(); dq.rotate(1)
deque(maxlen=3) # auto-evicting window
# heapq
h = [5, 1, 3]; heapq.heapify(h)
heapq.heappush(h, 2); heapq.heappop(h)
heapq.heappushpop(h, 4) # push then pop, one sift
heapq.heapreplace(h, 4) # pop then push
heapq.nlargest(3, h); heapq.nsmallest(3, h)
# max-heap: push -x | tuples break ties: (priority, tiebreak, item)
# bisect
bisect.bisect_left(a, x); bisect.bisect_right(a, x)
bisect.insort(a, x) # O(n) insert, keeps sorted
# Memoization
@lru_cache(maxsize=None) # or @cache in 3.9+
def f(i, j): ...
f.cache_clear()
# Arguments must be hashable -> pass tuples, not lists
# Sorting
a.sort(key=lambda x: (-x[1], x[0])) # desc by 1, asc by 0
sorted(words, key=cmp_to_key(lambda x, y: 1 if x + y < y + x else -1))
# Prefix sums in one line
list(accumulate([1, 2, 3])) # [1, 3, 6]
list(accumulate([1, 2, 3], initial=0)) # [0, 1, 3, 6]
list(accumulate(nums, max)) # running maximum
# Infinity and integer division
float('inf'), float('-inf'), math.inf
-7 // 2 # -4 (floors!) use int(-7/2) for -3
divmod(17, 5) # (3, 2)
# Grids
grid = [[0] * n for _ in range(m)] # NOT [[0]*n]*m (aliased rows)
for r, row in enumerate(grid):
for c, val in enumerate(row): ...
list(zip(*grid)) # transpose
# Recursion depth
import sys
sys.setrecursionlimit(10 ** 6)
# Strings
s.isalnum(); s.lower(); s[::-1]
"".join(chars) # never += in a loop
ord('a'), chr(97)
idx = ord(ch) - ord('a') # 26-length frequency arrays
# Tuple unpacking and swapping
a, b = b, a
for (x, y) in pairs: ...
# Walrus in while loops
# while (node := node.next): ...
Interview flow that scores well
- Restate the problem and confirm constraints, input ranges, and edge cases (empty, single element, duplicates, negatives, overflow).
- Say the brute force and its complexity out loud — establishes a baseline.
- Name the pattern and why it applies before writing code.
- State the target complexity, then implement.
- Dry-run on a small example and on one edge case.
- Mention the trade-off you'd make differently at scale (space vs. time, streaming vs. batch).
Edge cases to check every time: empty input · one element · all identical · already sorted / reverse sorted · negative numbers · integer overflow (not a Python issue, but interviewers ask) · duplicate keys · self-loops and disconnected components in graphs · cycles · k > n · target smaller than every element.