7 drills · 7 pattern exercises · 16 micro drills
Patterns used in this topic, with difficulty breakdown.
Starting from a pixel, change its color and all connected same-color pixels to a new color (like the paint bucket tool).
All 7 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Find the shortest path from one starting node to all other nodes in a graph with positive edge weights.
Always process the closest unfinished node first (via a min-heap). Once a node is popped, its shortest distance is finalized — greedy on distance.
Prompt
Given a weighted directed graph as an adjacency list and a source node, find the shortest distance to all other nodes using Dijkstra's algorithm.
Solution
import heapq
def dijkstra(graph, src):
dist = {src: 0}
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float('inf')):
continue # stale entry
for v, w in graph.get(u, []):
nd = d + w
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
# graph: {0: [(1,4),(2,1)], 1: [(3,1)], 2: [(1,2),(3,5)], 3: []}
# dijkstra(graph, 0) => {0:0, 1:3, 2:1, 3:4}In plain English: Order tasks so that every task comes after its prerequisites, using a queue-based approach.
Start with nodes having no prerequisites (in-degree 0). Process them, reduce neighbors' in-degrees, and add newly zero-degree nodes to the queue.
Prompt
Given a directed acyclic graph (DAG) as an adjacency list, return a topological ordering of its nodes using Kahn's algorithm (BFS-based).
Solution
from collections import deque
def topological_sort(graph, n):
in_deg = [0] * n
for u in range(n):
for v in graph.get(u, []):
in_deg[v] += 1
# seed queue with nodes that have no incoming edges (ready to process)
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph.get(u, []):
in_deg[v] -= 1
# neighbour becomes processable once all its prerequisites are done
if in_deg[v] == 0:
q.append(v)
return order if len(order) == n else [] # empty if cycle
# Test: {0:[1,2], 1:[3], 2:[3], 3:[]}, n=4 => [0,1,2,3] or [0,2,1,3]In plain English: Check if you can finish all courses given their prerequisite requirements (no circular dependencies).
Build a graph and run topological sort. If the resulting order has all n courses, no cycle exists. If fewer, a cycle blocks completion.
Prompt
Given n courses and prerequisite pairs [a, b] meaning 'take b before a', determine if all courses can be completed (detect if the dependency graph has a cycle).
Solution
from collections import deque
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
in_deg = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
in_deg[a] += 1
q = deque(i for i in range(num_courses) if in_deg[i] == 0)
count = 0
while q:
u = q.popleft()
count += 1
for v in graph[u]:
in_deg[v] -= 1
if in_deg[v] == 0:
q.append(v)
return count == num_courses # all courses processed = no cycle
# Test: can_finish(2, [[1,0]]) == True
# Test: can_finish(2, [[1,0],[0,1]]) == False (cycle)In plain English: Find an order to take all courses respecting prerequisites, or determine it's impossible.
Kahn's algorithm: compute in-degrees, start with zero in-degree nodes. Process each node by reducing neighbors' in-degrees. If all nodes are processed, we have a valid order; otherwise there's a cycle.
Prompt
Given numCourses and prerequisites pairs [a,b] meaning 'b before a', return a valid course ordering. Return [] if impossible (cycle exists).
Solution
from collections import deque, defaultdict
def find_order(num_courses, prerequisites):
# Kahn's algorithm: iteratively remove zero in-degree nodes to build a topological order
graph = defaultdict(list)
in_degree = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
# course becomes takeable once all its prerequisites are satisfied
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_courses else []
# Test: find_order(4, [[1,0],[2,0],[3,1],[3,2]])
# == [0,1,2,3] or [0,2,1,3] (valid topological orders)
# Test: find_order(2, [[0,1],[1,0]]) == [] (cycle)In plain English: Count separate groups of connected land cells in a grid.
Each unvisited '1' starts a new island. DFS/BFS from it marks all connected land as visited — the number of fresh DFS calls equals the number of islands.
Prompt
Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Solution
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 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] = '#' # mark visited
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
# Test: grid = [["1","1","0"],["1","0","0"],["0","0","1"]] => 2In 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: Make a complete copy of a graph where each node and its connections are duplicated.
Use a hashmap from original node to cloned node. DFS through the graph — if a neighbor is already cloned, reuse it; otherwise clone and recurse.
Prompt
Given a reference to a node in an undirected connected graph, return a deep copy of the graph. Each node has a value and a list of neighbors.
Solution
class GraphNode:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def clone_graph(node):
if not node:
return None
cloned = {}
def dfs(n):
if n in cloned:
return cloned[n]
copy = GraphNode(n.val)
cloned[n] = copy # map original -> clone
for nb in n.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)
# Test: graph 1--2--3--1 => cloned graph with same structure7 exercises: spot the signals, pick the method, avoid the trap.
Shortest path from source in a weighted graph.
Signals
Min-heap of (distance, node). Pop closest, relax edges. First pop of each node is shortest. O((V+E) log V).
BFS only works for unweighted graphs. For weighted, you MUST use Dijkstra or Bellman-Ford.
Trap
Using BFS on weighted graphs gives WRONG answers. The heap ensures you process closest first.
Return a topological ordering of a DAG.
Signals
Kahn's: queue nodes with in-degree 0. Process, reduce neighbors' in-degrees. Add newly zero-degree nodes. O(V+E).
DFS post-order reversed gives topological order. Also O(V+E).
Trap
If result has fewer than V nodes, the graph has a cycle (not a DAG).
Can all courses be completed given prerequisites? (Cycle detection in DAG.)
Signals
Run Kahn's algorithm. If all nodes are processed, no cycle → all courses completable. O(V+E).
DFS with 3-color marking (white/gray/black). Gray→Gray edge = cycle. O(V+E).
Trap
This IS a cycle detection problem in disguise. Model courses as a directed graph.
Count islands in a 2D grid of '1' (land) and '0' (water).
Signals
For each unvisited '1', run DFS to mark all connected land. Count DFS starts. O(m*n).
BFS from each unvisited '1' also works. Same counting logic, same O(m*n).
Trap
This is connected components on a grid. Grid = implicit graph where neighbors are adjacent cells.
Deep copy a graph. Each node has a value and neighbor list.
Signals
DFS with hashmap {original: clone}. For each neighbor: if cloned, reuse; else clone and recurse. O(V+E).
BFS with same hashmap approach. O(V+E).
Trap
Must handle cycles — the hashmap prevents infinite loops by checking if a node is already cloned.
Change all connected cells of the same color starting from (sr, sc).
Signals
DFS from (sr, sc). Change color, recurse on 4 neighbors matching original color. O(m*n).
BFS from start pixel also works. Same O(m*n).
Trap
If new_color == original_color, return immediately — otherwise infinite recursion.
Given n courses and prerequisites, return a valid order to take all courses, or empty if impossible.
Signals
Kahn's BFS: process nodes with in-degree 0. If result has fewer than n nodes, there's a cycle. O(V+E).
DFS with three states (unvisited/in-progress/done). Post-order gives reverse topological order. O(V+E).
Trap
Don't forget to detect cycles — if the topological order has fewer than n nodes, return empty.
16 quick recall drills to reinforce this topic.
Min-heap BFS for weighted graphs. Skip stale entries (d > dist[u]). O((V+E) log V). Non-negative weights only.
import heapq
from collections import defaultdict
def dijkstra(graph, src, n):
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue # stale entry
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return distheappop extracts the minimum. Pair with heappush for priority queue operations.
import heapq
heapq.heappop(h)Dijkstra from source k. Answer is max distance (time for signal to reach farthest node). -1 if not all reachable.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {k: 0}
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist.get(u, float('inf')): continue
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float('inf')):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return max(dist.values()) if len(dist) == n else -1BFS-based topo sort processes zero-indegree nodes first. Detects cycles if order is incomplete.
from collections import deque
q = deque(n for n in range(V) if indeg[n] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)Kahn's algorithm: start from zero in-degree nodes, peel layers. If len(order) < n, there's a cycle.
from collections import deque, defaultdict
in_deg = [0] * n
graph = defaultdict(list)
for a, b in edges:
graph[b].append(a)
in_deg[a] += 1
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
in_deg[nb] -= 1
if in_deg[nb] == 0:
q.append(nb)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))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()Undirected edges add both directions. Foundation for graph construction.
graph[u].append(v)
graph[v].append(u)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))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 countMove-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 wHashMap maps original → clone. DFS creates clone before recursing neighbors to handle cycles.
def cloneGraph(node):
if not node: return None
cloned = {}
def dfs(n):
if n in cloned: return cloned[n]
copy = Node(n.val)
cloned[n] = copy
for nb in n.neighbors:
copy.neighbors.append(dfs(nb))
return copy
return dfs(node)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)Recursive DFS on a grid with bounds + color check. Same pattern for island counting, connected regions, etc.
def fill(grid, i, j, old, new):
if i < 0 or i >= len(grid): return
if j < 0 or j >= len(grid[0]): return
if grid[i][j] != old: return
grid[i][j] = new
for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
fill(grid, i+di, j+dj, old, new)defaultdict eliminates key-existence checks. Simplifies grouping and adjacency list construction.
from collections import defaultdict
d = defaultdict(list)