BFS Fundamentals
BFS (Breadth-First Search) explores a graph level by level, visiting all nodes at distance 1 before distance 2, etc. This guarantees the shortest path (fewest hops) in an unweighted graph. Implementation: use a deque (double-ended queue) for O(1) popleft. Mark nodes visited on enqueue (not on dequeue) to prevent re-processing. Visited set is critical — without it, BFS loops forever on cyclic graphs.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([(start, 0)]) # (node, distance)
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
BFS vs DFS: BFS finds shortest paths (unweighted), uses more memory (stores an entire level). DFS finds any path, uses less memory (only the current path). Use BFS when the question asks for shortest, minimum steps, or minimum distance.
Number of Islands (LC 200)
Grid BFS: treat each cell as a graph node with neighbors up/down/left/right. Count the number of connected components of land cells (value=1). For each unvisited land cell, run BFS and mark all reachable land cells as visited. Increment the island count.
def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
visited = set()
count = 0
def bfs(r, c):
q = deque([(r, c)])
visited.add((r, c))
while q:
row, col = q.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = row+dr, col+dc
if 0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and grid[nr][nc] == '1':
visited.add((nr, nc))
q.append((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r,c) not in visited:
bfs(r, c)
count += 1
return countWord Ladder (LC 127)
Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, using only words in the word list. BFS state = current word. Neighbors = all words that differ by exactly one letter. Optimization: instead of comparing all word pairs O(n^2), use a wildcard pattern map. For “hot”: generate patterns “?ot”, “h?t”, “ho?” — index all words under their patterns. Transition from “hot”: look up all words matching each pattern. BFS from beginWord to endWord. Return the level count when endWord is reached. Bidirectional BFS optimization: run BFS simultaneously from beginWord and endWord. Stop when the frontiers intersect. Reduces time complexity from O(b^d) to O(b^(d/2)) where b=branching factor, d=depth.
Multi-Source BFS
When the shortest distance from any source (multiple starting points) to each cell is needed: initialize the BFS queue with all sources at distance 0. Run BFS normally. Each cell records the distance to the nearest source. This is O(V+E) for one pass, vs O(S * (V+E)) for running BFS from each source separately. LC 286 (Walls and Gates): multi-source BFS from all gates (value=0) to fill the distance to the nearest gate in each empty room. LC 994 (Rotting Oranges): multi-source BFS from all rotten oranges simultaneously to find when all fresh oranges rot. LC 542 (01 Matrix): multi-source BFS from all 0-cells to find the distance of each 1-cell to the nearest 0-cell.
BFS on States (Not Just Nodes)
Some problems require BFS over states rather than nodes in a fixed graph. LC 752 (Open the Lock): 4-digit combination lock. State = “0000” to “9999”. Transitions = turning one wheel up or down (+1 or -1 mod 10). BFS from “0000” to the target, avoiding “deadends”. Each state is a string; visited set stores strings. 10^4 states, 8 transitions each — manageable. LC 1197 (Minimum Knight Moves): BFS on (row, col) states with 8 possible knight moves. Key optimization: normalize coordinates to one quadrant (problem is symmetric) to reduce state space from infinity to bounded. Always check: is the state space finite and small enough for BFS? State space size * branching factor must be feasible (< ~10^7).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide