8 drills · 8 pattern exercises · 17 micro drills
Patterns used in this topic, with difficulty breakdown.
Walk every reachable node in a graph by going as deep as possible before backtracking, using a stack.
All 8 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Find the fewest edges to get from a starting node to every other node in an unweighted graph.
BFS explores all nodes at distance d before d+1 — the first time you reach any node is guaranteed to be the shortest path.
Prompt
Find shortest distances from a start node in an unweighted graph.
Solution
from collections import deque
def bfs_dist(graph, start):
dist = {start: 0}
q = deque([start])
while q:
node = q.popleft()
for nb in graph[node]:
if nb not in dist:
dist[nb] = dist[node] + 1 # first visit = shortest distance
q.append(nb)
return dist
# Test: bfs_dist({0:[1,2], 1:[0,3], 2:[0], 3:[1]}, 0)
# => {0:0, 1:1, 2:1, 3:2}In 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: Walk every reachable node in a graph by going as deep as possible before backtracking, using recursion.
The call stack acts as an implicit stack — each recursive call goes one level deeper before backtracking.
Prompt
Traverse a graph depth-first using recursion.
Solution
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node) # mark before recursing to prevent revisits
for nb in graph[node]:
if nb not in visited:
dfs(graph, nb, visited) # call stack acts as implicit stack
return visitedIn plain English: Determine whether an undirected graph contains any loop.
In DFS, a visited neighbor that isn't your parent means you've found a back edge — proof that a cycle exists.
Prompt
Detect if an undirected graph contains a cycle.
Solution
def has_cycle(graph, n):
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node):
return True
elif nb != parent: # visited + not parent = back edge = cycle
return True
return False
for i in range(n):
if i not in visited:
if dfs(i, -1):
return True
return FalseIn plain English: Count how many disconnected groups of nodes exist in a graph.
Each DFS from an unvisited node discovers one full connected component — the count of fresh traversals equals the number of components.
Prompt
Count the number of connected components in an undirected graph.
Solution
def count_components(graph, n):
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph.get(node, []):
if nb not in visited:
dfs(nb)
for i in range(n):
if i not in visited:
# new traversal = new component
dfs(i)
count += 1
return count
# Test: {0:[1], 1:[0], 2:[3], 3:[2], 4:[]}, n=5 => 3In plain English: Find the minimum number of dice rolls to reach square 100 on a snakes-and-ladders board.
Model the board as a graph where each square connects to the 6 dice outcomes — BFS then finds the minimum rolls to reach 100.
Prompt
Find minimum dice rolls to reach square 100 on a snakes-and-ladders board.
Solution
from collections import deque
def snakes_ladders(board):
# board: dict {position: destination}
target = 100
dist = {1: 0}
q = deque([1])
while q:
pos = q.popleft()
if pos == target:
return dist[pos]
for dice in range(1, 7): # each dice roll = one edge
nxt = pos + dice
if nxt > target:
continue
if nxt in board:
nxt = board[nxt]
if nxt not in dist:
dist[nxt] = dist[pos] + 1
q.append(nxt)
return -1In plain English: Rotten oranges spread to adjacent fresh oranges each minute. How long until all are rotten?
Multi-source BFS: start by enqueueing all rotten oranges simultaneously. Each BFS level = one minute. Track fresh count; if it reaches 0, return the number of minutes elapsed.
Prompt
In a grid, 0=empty, 1=fresh orange, 2=rotten orange. Each minute, fresh oranges adjacent to rotten ones also rot. Return the minutes until no fresh oranges remain, or -1 if impossible.
Solution
from collections import deque
def oranges_rotting(grid):
m, n = len(grid), len(grid[0])
# multi-source BFS: all rotten cells enqueued at time 0 so rot spreads simultaneously
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
while queue:
minutes += 1
# process entire current wavefront before advancing the clock
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 2
fresh -= 1
queue.append((nx, ny))
return minutes - 1 if fresh == 0 else -1
# Test: oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) == 4
# Test: oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) == -1In plain English: Flip all O regions to X, except those connected to the border of the board.
Reverse thinking: instead of finding surrounded regions, find unsurrounded ones. DFS/BFS from all border 'O's, marking them safe. Then flip all remaining 'O' to 'X' and restore safe cells.
Prompt
Given an m x n board of 'X' and 'O', capture all regions of 'O' that are completely surrounded by 'X' (flip them to 'X'). Border-connected 'O's should not be captured.
Solution
def solve(board):
if not board:
return
m, n = len(board), len(board[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
return
board[i][j] = 'S' # mark as safe
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
# Mark border-connected O's as safe
for i in range(m):
dfs(i, 0); dfs(i, n - 1)
for j in range(n):
dfs(0, j); dfs(m - 1, j)
# Flip: O -> X (captured), S -> O (safe)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'S':
board[i][j] = 'O'
return board
# Test: solve([["X","X","X","X"],["X","O","O","X"],
# ["X","X","O","X"],["X","O","X","X"]])
# => [["X","X","X","X"],["X","X","X","X"],
# ["X","X","X","X"],["X","O","X","X"]]8 exercises: spot the signals, pick the method, avoid the trap.
Find shortest distances from a start node in an unweighted graph.
Signals
BFS from start with distance tracking. First visit = shortest distance. O(V+E).
Dijkstra works but is overkill for unweighted graphs. BFS is simpler and equally efficient.
Trap
DFS does NOT give shortest paths. BFS's level-by-level exploration is what guarantees it.
Traverse a graph depth-first using an explicit stack.
Signals
Push start, loop: pop, visit if unvisited, push neighbors. O(V+E).
Trap
Don't forget the visited set — without it, cycles cause infinite loops.
Traverse a graph depth-first using recursion.
Signals
Visit node, mark visited, recurse on unvisited neighbors. O(V+E).
Iterative DFS with explicit stack — avoids stack overflow on very deep graphs.
Trap
Python's recursion limit (default 1000) can be hit on large graphs. sys.setrecursionlimit or use iterative.
Detect if an undirected graph contains a cycle.
Signals
DFS tracking parent. If a neighbor is visited and not the parent → cycle found. O(V+E).
BFS with parent tracking also works. Same logic: visited non-parent neighbor = cycle.
Trap
In undirected graphs, every edge appears twice. You must track the parent to avoid false positives.
Count the number of connected components in an undirected graph.
Signals
For each unvisited node, run DFS to mark its component. Count the number of DFS calls. O(V+E).
BFS works identically — just a different traversal strategy for the same counting approach.
Trap
Don't forget disconnected nodes — iterate over ALL nodes, not just starting from node 0.
Find minimum dice rolls to reach square 100 on a snakes-and-ladders board.
Signals
Model board as graph. BFS from square 1. Each node has edges to squares +1 through +6 (with redirects). O(n).
Trap
This IS a graph problem in disguise. The key insight is modeling the board as a graph.
In a grid, fresh oranges rot when adjacent to rotten ones. Find the minimum minutes for all to rot.
Signals
Add all rotten oranges to queue at time 0. BFS spreading rot. Track max time. O(m*n).
DFS from each rotten orange updating min time — but BFS is cleaner for simultaneous spread.
Trap
Don't BFS from one rotten orange at a time — they all spread SIMULTANEOUSLY. Multi-source BFS.
Given a board of 'X' and 'O', capture all regions surrounded by 'X' (flip 'O' to 'X'), except those connected to the border.
Signals
Mark border-connected O's as safe (DFS from borders). Then flip all remaining O's to X. O(m*n).
BFS from border O's. Same logic.
Trap
Don't try to detect 'surrounded' regions directly. Instead, find 'unsurrounded' from the border and flip the rest.
17 quick recall drills to reinforce this topic.
BFS guarantees shortest path in unweighted grid. Mark visited WHEN ADDING to queue (not when popping). O(m*n).
from collections import deque
def shortestPath(grid, start, end):
m, n = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = {(start[0], start[1])}
while q:
r, c, dist = q.popleft()
if (r, c) == tuple(end):
return dist
for dr, dc in (0,1),(0,-1),(1,0),(-1,0):
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and grid[nr][nc] == 0
and (nr, nc) not in visited):
visited.add((nr, nc))
q.append((nr, nc, dist + 1))
return -1BFS explores level-by-level. Gives shortest path in unweighted graphs.
from collections import deque
q = deque([start])
visited = {start}
while q:
node = q.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
q.append(nb)Deque gives O(1) operations at both ends. Essential for BFS and sliding window.
from collections import deque
q = deque()
q.append(x)
q.popleft()Iterative DFS avoids recursion limits. Same time complexity, explicit stack.
stack = [start]
visited = {start}
while stack:
node = stack.pop()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
stack.append(nb)Recursive DFS is the most natural graph traversal. Watch for stack overflow on deep graphs.
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.
stack = []
stack.append(x)
stack.pop()Flood-fill DFS: mark visited by changing '1' to '0'. Each DFS call covers one island. Count DFS starts.
def numIslands(grid):
m, n = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0' # mark visited
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return countTrack parent to avoid counting the edge we came from. If neighbor is visited and not parent → cycle.
def hasCycleUndirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
def dfs(u, parent):
visited[u] = True
for v in graph[u]:
if not visited[v]:
if dfs(v, u): return True
elif v != parent: # visited and not parent → cycle
return True
return False
return any(not visited[i] and dfs(i, -1) for i in range(n))Undirected edges add both directions. Foundation for graph construction.
graph[u].append(v)
graph[v].append(u)Loop over all nodes, DFS/BFS from unvisited ones, increment count each time. Works on adjacency list or matrix.
visited = set()
count = 0
for node in range(n):
if node not in visited:
count += 1
stack = [node]
while stack:
cur = stack.pop()
if cur in visited: continue
visited.add(cur)
stack.extend(graph[cur])Recursive node counting teaches divide-and-conquer tree thinking.
def count(node):
if not node: return 0
return 1 + count(node.left) + count(node.right)Initialize queue with all sources. BFS radiates outward in parallel from all starting points.
q = deque()
for i in range(R):
for j in range(C):
if grid[i][j] == 2: q.append((i, j, 0))
while q:
i, j, t = q.popleft()
for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
ni, nj = i+di, j+dj
if 0<=ni<R and 0<=nj<C and grid[ni][nj]==1:
grid[ni][nj] = 2
q.append((ni, nj, t+1))Level-order BFS uses a queue with size tracking. Core pattern for tree breadth-first problems.
from collections import deque
q = deque([root])
while q:
for _ in range(len(q)):
node = q.popleft()
if node.left: q.append(node.left)
if node.right: q.append(node.right)Sortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))Start DFS from border O's to mark safe cells. Everything else gets captured.
for i in range(R):
for j in range(C):
if (i in (0, R-1) or j in (0, C-1)) and board[i][j] == 'O':
dfs(i, j) # mark border O as safeMove-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return w