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).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why do we mark nodes as visited when they are enqueued, not when they are dequeued?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “If we mark nodes visited only when dequeued (popped from the queue), the same node can be added to the queue multiple times — once by each neighbor that discovers it. For a graph with N nodes and E edges, this means O(E) enqueue operations instead of O(N). In the worst case (dense graphs), this causes O(E) memory usage and O(E) processing time per BFS call instead of O(V+E) total. Marking as visited on enqueue prevents a node from being added to the queue more than once. The invariant: a node is in the visited set if and only if it has been or is currently in the queue. This ensures each node is processed exactly once, giving the correct O(V+E) time complexity.”
}
},
{
“@type”: “Question”,
“name”: “How does multi-source BFS differ from running BFS from each source separately?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Single-source BFS from one source: O(V+E). Running BFS from each of S sources separately: O(S * (V+E)). Multi-source BFS: initialize the queue with all S sources at distance 0 simultaneously. Run one BFS pass. Each cell is labeled with the distance to the nearest source. Total time: O(V+E). The key insight: all sources are at distance 0, so BFS explores level by level from all of them simultaneously, as if there were one virtual super-source connected to all real sources with zero-cost edges. Use multi-source BFS whenever the problem asks for the minimum distance from any member of a set of sources to each node: nearest gate (LC 286), rotting oranges (LC 994), 01 matrix (LC 542). It is always more efficient than S separate BFS calls.”
}
},
{
“@type”: “Question”,
“name”: “When should you use bidirectional BFS?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Bidirectional BFS explores from both the source and the target simultaneously, stopping when the two frontiers meet. In a graph where each node has branching factor b and the shortest path has length d, regular BFS explores O(b^d) nodes. Bidirectional BFS explores O(b^(d/2)) nodes from each end — the frontiers meet after d/2 steps each. Total: O(b^(d/2) + b^(d/2)) = O(b^(d/2)), a dramatic reduction for large d. Use when: the graph is large and the target is known, the branching factor is high, and d is large. Word Ladder (LC 127) is the canonical example. Implementation: maintain two visited sets and two queues. At each step, expand the smaller frontier (to minimize total work). Stop and compute the path when a node in one frontier is found in the other.”
}
},
{
“@type”: “Question”,
“name”: “How do you find the shortest path with obstacles (LC 1293)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Standard BFS state (row, col) does not account for which obstacles have been eliminated. Extend the state to (row, col, eliminations_used). BFS over this 3D state space. visited = set() of (row, col, k) where k = number of obstacles eliminated so far. Enqueue (row, col, k, distance). For each cell: if it is an obstacle and k < K (max allowed), add it to the queue with k+1 eliminations. If it is open, add with the same k. State space: O(rows * cols * K). BFS still finds the shortest path because each state transition adds 1 to the distance. This pattern generalizes: extend the BFS state with any additional constraint (number of keys collected, fuel remaining, special moves used). The state space must be finite and small enough to process."
}
},
{
"@type": "Question",
"name": "How do you reconstruct the actual shortest path in BFS, not just its length?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Track a parent dictionary: parent[node] = the node from which this node was first reached. When enqueueing a neighbor, set parent[neighbor] = current_node. To reconstruct the path: start from the target, follow parent pointers back to the source. Reverse the resulting list. In grid problems: parent[(nr, nc)] = (row, col). For word ladder: parent[word] = previous_word. If the path itself is not needed, only the parent of the target matters. Edge case: if there are multiple shortest paths, the parent dict stores one arbitrary path (the one that was discovered first). To find all shortest paths: use a BFS that tracks all parents per node (parent[node] = set of predecessors at the same minimum distance). Then DFS or BFS backwards through the DAG of shortest paths."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide