22 drills. One per topic. The essential checklist — if you can write these cold, you have the building blocks for everything else.
In plain English: Count the number of ways to walk from the top-left to the bottom-right of a grid, only moving right or down.
dp[i][j] = number of ways to reach cell (i,j). Each cell can only come from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. Optimize to a single row since we only look at the previous row.
Prompt
A robot is in the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?
Solution
def unique_paths(m, n):
row = [1] * n # base: top row all 1s
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1] # above + left
return row[-1]
# Test: unique_paths(3, 7) == 28
# Test: unique_paths(3, 2) == 3In plain English: Starting from a pixel, change its color and all connected same-color pixels to a new color (like the paint bucket tool).
DFS from the starting pixel, changing color as you go. Only recurse into neighbors that match the original color — naturally stops at boundaries.
Prompt
Given a 2D image grid, a starting pixel (sr, sc), and a new color, flood fill the connected region of the starting pixel's color with the new color.
Solution
def flood_fill(image, sr, sc, new_color):
orig = image[sr][sc]
if orig == new_color:
return image
m, n = len(image), len(image[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or image[i][j] != orig:
return
image[i][j] = new_color # fill
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
dfs(sr, sc)
return image
# Test: flood_fill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)
# => [[2,2,2],[2,2,0],[2,0,1]]In plain English: Find the longest path between any two nodes in a binary tree, measured in edges.
At each node, the longest path through it is left_height + right_height. Track the global maximum while computing heights bottom-up.
Prompt
Find the diameter of a binary tree — the length of the longest path between any two nodes (in edges).
Solution
def diameter_of_binary_tree(root):
diameter = [0]
def height(node):
if not node:
return 0
lh = height(node.left)
rh = height(node.right)
diameter[0] = max(diameter[0], lh + rh) # path through this node
return 1 + max(lh, rh)
height(root)
return diameter[0]
# Test: tree [1,2,3,4,5] => diameter = 3 (path 4->2->1->3)In plain English: You're given a list of numbers and need to flip the order without creating a new list.
Two pointers converging from opposite ends is the go-to for symmetric array operations — each swap brings both ends closer to the center.
Prompt
Given an array a, reverse it in-place.
Solution
def reverse(a):
l, r = 0, len(a) - 1
# converge from both ends
while l < r:
a[l], a[r] = a[r], a[l]
l += 1
r -= 1
return a
# Test: reverse([1,2,3,4,5]) == [5,4,3,2,1]In plain English: Given phone number digits, list all possible letter combinations from the keypad (like T9).
Each digit maps to 3-4 letters. Build combinations by choosing one letter per digit and backtracking — the recursion tree has at most 4^n leaves.
Prompt
Given a string of digits 2-9, return all possible letter combinations that the number could represent (phone keypad mapping).
Solution
def letter_combinations(digits):
if not digits:
return []
phone = {'2':'abc','3':'def','4':'ghi','5':'jkl',
'6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
result = []
def backtrack(idx, path):
if idx == len(digits):
result.append(''.join(path))
return
for c in phone[digits[idx]]:
path.append(c)
backtrack(idx + 1, path)
path.pop() # backtrack
backtrack(0, [])
return result
# Test: letter_combinations("23") == ["ad","ae","af","bd","be","bf","cd","ce","cf"]In plain English: Look for a specific number in a sorted list by repeatedly cutting the search area in half.
Each comparison eliminates half the remaining elements — log2(n) halves is all you ever need to find any element or prove it absent.
Prompt
Given a sorted array and a target value, return the index of the target or -1 if not found.
Solution
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1 # target is in right half
else:
hi = mid - 1 # target is in left half
return -1
# Test: binary_search([1,3,5,7,9,11], 7) == 3
# Test: binary_search([1,3,5,7,9,11], 4) == -1In plain English: Count how many 1s appear in the binary form of a number.
n & (n-1) clears the lowest set bit each time — loop until n is zero and count the iterations.
Prompt
Count the number of 1-bits (set bits) in the binary representation of a non-negative integer.
Solution
def count_bits(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Test: count_bits(11) == 3 (1011 in binary)
# Test: count_bits(128) == 1 (10000000)
# Test: count_bits(0) == 0In plain English: Count the number of different ways to reach the top of a staircase if you can take 1 or 2 steps at a time.
To reach step n you came from step n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2) — the same recurrence as Fibonacci.
Prompt
You can climb 1 or 2 steps at a time. How many distinct ways can you climb n stairs?
Solution
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b # ways[i] = ways[i-1] + ways[i-2]
return b
# Test: climb_stairs(2) == 2
# Test: climb_stairs(3) == 3
# Test: climb_stairs(5) == 8In plain English: Walk every reachable node in a graph by going as deep as possible before backtracking, using a stack.
Replacing the BFS queue with a stack switches from breadth-first to depth-first — LIFO explores deep before wide.
Prompt
Traverse a graph depth-first using an explicit stack.
Solution
def dfs_iterative(graph, start):
visited = {start}
stack = [start] # stack = LIFO = depth first
order = []
while stack:
node = stack.pop()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)
return orderIn plain English: Find the best day to buy and the best day to sell a stock to make the most money.
Track the minimum price seen so far. At each day, the best you can do is sell at today's price minus the cheapest buy — one pass, O(1) space.
Prompt
Given an array of stock prices (one per day), find the maximum profit from one buy and one sell (buy before sell).
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for p in prices:
min_price = min(min_price, p)
max_profit = max(max_profit, p - min_price) # sell today, bought at min
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy at 1, sell at 6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)In plain English: Find two numbers in an unsorted list that add up to a target and return their indices.
Instead of checking all pairs O(n²), store each value in a hashmap — then lookup for the complement is O(1).
Prompt
Given unsorted array a and target t, return indices of the pair that sums to t.
Solution
def two_sum(a, t):
seen = {}
for i, x in enumerate(a):
# check complement before storing
if t - x in seen:
return [seen[t - x], i]
seen[x] = i
return []
# Test: two_sum([2,7,11,15], 9) == [0, 1]In plain English: Show how to add and remove elements from a min-heap, which always gives you the smallest element first.
A heap is a complete binary tree stored in an array where each parent is smaller than its children — push and pop maintain this property in O(log n).
Prompt
Demonstrate pushing and popping elements from a min-heap using Python's heapq module.
Solution
import heapq
def heap_demo():
h = []
for val in [5, 3, 8, 1, 2]:
heapq.heappush(h, val) # O(log n) insert
# h is now a valid min-heap
result = []
while h:
result.append(heapq.heappop(h)) # O(log n) extract-min
return result
# Test: heap_demo() == [1, 2, 3, 5, 8]In plain English: Check if any meetings in your schedule overlap with each other.
Sort by start time, then check each consecutive pair. If any meeting starts before the previous one ends, there's a conflict. Sorting makes the check O(n).
Prompt
Given an array of meeting time intervals [[start, end], ...], determine if a person could attend all meetings (i.e., no two meetings overlap).
Solution
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]: # overlap
return False
return True
# Test: can_attend_meetings([[0,30],[5,10],[15,20]]) == False
# Test: can_attend_meetings([[7,10],[2,4]]) == TrueIn plain English: Add a new node at a specific position in a linked list.
In a linked list, insertion is O(1) once you're at the right spot — the cost is in walking there.
Prompt
Insert value val at position k (0-indexed) in a linked list.
Solution
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def insert_at(head, val, k):
new = Node(val)
if k == 0:
new.next = head
return new
cur = head
for _ in range(k - 1):
cur = cur.next
# splice new node in
new.next = cur.next
cur.next = new
return head
# Test: 1->2->3, insert 9 at k=1 => 1->9->2->3In plain English: Keep replacing a number with the sum of the squares of its digits. It's happy if you eventually reach 1.
The sequence either converges to 1 or enters a cycle. Use Floyd's cycle detection (slow/fast pointers) or a hash set to detect the cycle. If you hit 1, it's happy.
Prompt
Write an algorithm to determine if a number n is happy. A happy number is defined by repeatedly summing the squares of its digits until you reach 1 or loop endlessly.
Solution
def is_happy(n):
def digit_sq_sum(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
# Floyd's cycle detection: fast moves 2 steps, slow 1
slow = n
fast = digit_sq_sum(n)
while fast != 1 and slow != fast:
slow = digit_sq_sum(slow)
fast = digit_sq_sum(digit_sq_sum(fast)) # two steps so it laps slow if a cycle exists
return fast == 1
# Test: is_happy(19) == True (19->82->68->100->1)
# Test: is_happy(2) == FalseIn plain English: Compute the nth Fibonacci number without redundantly recalculating the same sub-values.
Naive recursion recomputes fib(k) exponentially many times — memoization stores each result once, collapsing O(2^n) to O(n).
Prompt
Compute the nth Fibonacci number efficiently.
Solution
# Recursive + memo
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2) # store to avoid recomputation
return memo[n]
# Iterative (O(1) space)
def fib_iter(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Test: fib(10) == 55In plain English: Find the best day to buy and the best later day to sell a stock to maximize your profit.
Track the minimum price seen so far and compute profit at each step. This is Kadane's algorithm in disguise — the max gain ending here is today's price minus the running minimum.
Prompt
Given an array prices where prices[i] is the price of a stock on the ith day, return the maximum profit you can achieve from one buy and one sell. You must buy before you sell.
Solution
def max_profit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price) # track cheapest buy
max_profit = max(max_profit, price - min_price) # best sell
return max_profit
# Test: max_profit([7,1,5,3,6,4]) == 5 (buy@1, sell@6)
# Test: max_profit([7,6,4,3,1]) == 0 (no profit possible)In plain English: Sort a list by repeatedly picking the next element and inserting it into its correct spot.
Builds the sorted portion one element at a time by shifting — efficient for nearly-sorted data because few shifts are needed.
Prompt
Sort an array using insertion sort.
Solution
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift larger elements right
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
# Test: insertion_sort([5,3,1,4,2]) == [1,2,3,4,5]In plain English: Calculate the result of a math expression written in postfix notation like '2 1 + 3 *'.
Postfix notation eliminates the need for parentheses and precedence — operands are always ready on the stack when an operator appears.
Prompt
Evaluate a postfix (reverse Polish notation) expression.
Solution
def eval_postfix(tokens):
stack = []
ops = {'+': lambda a,b: a+b, '-': lambda a,b: a-b,
'*': lambda a,b: a*b, '/': lambda a,b: int(a/b)}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop() # pop order matters: b first, then a
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]
# Test: eval_postfix(["2","1","+","3","*"]) == 9In plain English: Add a new value to a binary search tree so that the BST property is preserved.
BST property guides you left or right at each node — the first None you reach is where the new node belongs.
Prompt
Insert a value into a binary search tree.
Solution
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bst_insert(root, val):
if root is None: # None = empty slot, insert here
return TreeNode(val)
if val < root.val:
root.left = bst_insert(root.left, val)
else:
root.right = bst_insert(root.right, val)
return rootIn plain English: Build a tree-like structure where each path from root to a node represents a prefix of inserted words. Support inserting words and checking if a word or prefix exists.
Each node is a dictionary of children keyed by character. Insert walks the tree creating nodes; search walks and checks the end marker. Prefix search is just search without the end check.
Prompt
Implement a trie with insert, search, and startsWith methods.
Solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
# create missing child nodes along the path for each character
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self._find(word)
# must land on a node AND it must be a complete word, not just a prefix
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def _find(self, prefix):
# traverse character-by-character; return None early if path doesn't exist
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
# Test: t = Trie(); t.insert("apple")
# t.search("apple") == True; t.search("app") == False
# t.starts_with("app") == TrueIn plain English: Remove duplicate values from a sorted list in-place and return how many unique values remain.
Slow pointer marks the write position, fast pointer scans ahead. When fast finds a new value, write it at slow+1 and advance slow. The sorted order guarantees duplicates are adjacent.
Prompt
Given a sorted array nums, remove the duplicates in-place such that each element appears only once. Return the new length.
Solution
def remove_duplicates(nums):
if not nums:
return 0
slow = 0 # slow = next write position for a unique value
for fast in range(1, len(nums)): # fast scans ahead for new values
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Test: nums = [1,1,2]; remove_duplicates(nums) == 2; nums[:2] == [1,2]
# Test: nums = [0,0,1,1,1,2,2,3,3,4]
# remove_duplicates(nums) == 5; nums[:5] == [0,1,2,3,4]