Graphs: BFS and DFS
Think of a map of friendships: you, your friends, and their friends, connected by lines. Finding out if two people are connected, or how many steps separate them, means walking those lines without retracing your steps. That is graph traversal, the single most reused pattern in interviews. Grids, dependency chains, social networks, and state-space search all reduce to "visit nodes without visiting the same one twice."
Two ways to draw a graph in code
A graph is a set of nodes (vertices) connected by edges. You almost always represent it one of two ways.
Adjacency list: a dict or array mapping each node to its neighbors.
from collections import defaultdict
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit this line for a directed graph
print(dict(graph))
# {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}Adjacency matrix: an n x n grid where matrix[i][j] = 1 if an edge exists.
n = 4
matrix = [[0] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| "Are u, v connected?" | O(degree(u)) | O(1) |
| Iterate neighbors of u | O(degree(u)) | O(V) |
| Best for | Sparse graphs (most interview problems) | Dense graphs, small V, or when you need O(1) edge lookup |
Pitfall: grid problems (Number of Islands, Rotting Oranges) don't hand you a graph object at all. The 2D grid itself is the implicit adjacency structure, with a cell's neighbors being the 4 (or 8) cells around it. Recognizing that a grid IS a graph is half the battle.
Remember: most interview graphs are sparse, so default to an adjacency list. A grid is a graph in disguise; its cells are nodes, adjacency is "next door."
Choosing BFS or DFS
Both visit every reachable node exactly once, but they explore in different orders and answer different questions.
| BFS | DFS | |
|---|---|---|
| Data structure | Queue (FIFO) | Stack (explicit) or recursion (call stack) |
| Explores | Level by level, outward from the source | One path all the way down before backtracking |
| Use for | Shortest path in an unweighted graph, "minimum steps", spreading from multiple sources | Path existence, connected components, cycle detection, backtracking, topological order |
| Space | O(V), can hold a full level | O(V) worst case (deep recursion), often less for wide, shallow graphs |
Rule of thumb: if the question says "shortest," "minimum," or "fewest steps," reach for BFS. If it says "does a path exist," "find all paths," or "explore everything," DFS, often recursive, is simpler to write and reason about.
Remember: "shortest" or "fewest steps" means BFS. "Does a path exist" or "find all X" means DFS.
Marking nodes visited at the right moment
Without tracking visited nodes, a cyclic graph causes an infinite loop. The detail interviewers probe hardest: mark a node visited the moment you enqueue or push it, not when you pop it.
from collections import deque
def bfs(graph, start):
visited = {start} # mark on enqueue
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # mark here, not after popping
queue.append(neighbor)
return orderMark visited only at pop time instead, and the same node can land in the queue multiple times before it's ever processed. That's wasted work at best, and in multi-source variants it can produce wrong answers. For grids, visited is usually a 2D boolean array, or you mutate the grid in place (flipping '1' to '0', say) to save space.
Remember: mark visited at enqueue/push time, not at pop/process time. Marking late lets duplicates pile into the queue.
Number of Islands
LeetCode 200, DFS/BFS, Grid traversal
Each connected group of '1's is one island. Scan every cell; whenever you find an unvisited '1', that's a brand-new island, so flood-fill it (DFS or BFS) to mark every connected land cell and avoid counting it twice.
Approach: Iterate all cells. On an unvisited land cell, increment the island count and run DFS/BFS to sink the entire connected component (mutate it to '0' as "visited").
def numIslands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # sink it so we never revisit
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
islands += 1
dfs(r, c)
return islandsComplexity: Time O(rows × cols), each cell is visited a constant number of times. Space O(rows × cols) worst case for the recursion stack, when the grid is entirely land.
Common mistakes: Forgetting boundary checks before indexing, which crashes with an out-of-range error. Mutating the grid without realizing the interviewer may not want the input destroyed; mention the trade-off and offer a separate visited set as an alternative. Using DFS recursion on a huge grid can hit a recursion-depth limit, something BFS with an explicit queue avoids entirely.
Remember: scan every cell; each unvisited land cell you find starts a new island. Flood-fill it so you never count it again.
Clone Graph
LeetCode 133, BFS/DFS, Deep copy
You must build a completely new graph with new node objects, while preserving the same connections. The trick is avoiding infinite loops on cycles: keep a map from original node to cloned node so you never clone the same node twice.
Approach: BFS or DFS from the given start node. Use a hash map old -> new. Whenever you meet a neighbor you haven't cloned yet, create its clone and enqueue it; either way, append the clone to the current node's clone's neighbor list.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: 'Node') -> 'Node':
if not node:
return None
old_to_new = {node: Node(node.val)}
queue = deque([node])
while queue:
cur = queue.popleft()
for neighbor in cur.neighbors:
if neighbor not in old_to_new:
old_to_new[neighbor] = Node(neighbor.val)
queue.append(neighbor)
old_to_new[cur].neighbors.append(old_to_new[neighbor])
return old_to_new[node]Complexity: Time O(V + E), space O(V) for the map and queue.
Common mistakes: Cloning a neighbor's value instead of wiring up the actual clone object. Not handling the single-node-with-no-neighbors edge case. Re-cloning a node already in the map; always check the map before creating a new Node.
Remember: a map from old node to new node is what stops a cycle from cloning the same node twice, or looping forever.
Rotting Oranges
LeetCode 994, BFS, Multi-source BFS
Every rotten orange rots its fresh neighbors at the same time, one minute at a time. That is BFS starting from multiple sources at once: seed the queue with every initially-rotten orange, then expand level by level, where each level equals exactly one minute.
Approach: Push all rotten cells into the queue first (minute 0). Track the fresh count. BFS level by level; each level that rots at least one orange increments the minute counter. If fresh > 0 after the BFS runs out, return -1.
def orangesRotting(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)): # process one full level = one minute
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1Complexity: Time O(rows × cols), space O(rows × cols) for the queue.
Common mistakes: Incrementing minutes even on a final level where nothing new rotted. The level-batching pattern above handles this correctly; verify it against the "no fresh oranges at all" edge case, which should return 0. Forgetting multi-source seeding and instead running BFS from just one rotten cell.
Remember: seed the queue with every rotten orange at once. One BFS level equals exactly one minute passing.
Walls and Gates
LeetCode 286, BFS, Fill distances
Same multi-source BFS pattern as Rotting Oranges, but instead of counting minutes, you write the BFS depth directly into each empty room as its distance to the nearest gate.
Approach: Seed the queue with every gate (value 0). BFS outward; whenever you reach an empty room (INF), set its distance to current_distance + 1 and enqueue it.
INF = 2147483647
def wallsAndGates(rooms: list[list[int]]) -> None:
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
queue = deque()
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0:
queue.append((r, c))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))Complexity: Time O(rows × cols), space O(rows × cols).
Common mistakes: Running BFS separately from every gate instead of seeding all gates into one shared queue. That still gives the correct answer, but it costs O(gates × cells) instead of O(cells); mention the multi-source optimization explicitly, since interviewers look for it. Walls (-1) should simply be skipped, not treated as an error case.
Remember: seed every gate into one shared queue, one BFS. Don't run a separate BFS per gate.