Breadth‑First Search Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When an interview problem talks about the fewest moves, the shortest distance, or any kind of "closest" relationship, it is often a cue to reach for Breadth‑First Search (BFS). Unlike Depth‑First Search, which dives deep before backtracking, BFS expands outward layer by layer. This property guarantees that the first time you reach a target, you have done so with the minimum number of steps. Below we break down the pattern, walk through a concrete Python implementation, discuss complexity and common mistakes, and finish with five curated practice problems.

What BFS Actually Does

BFS treats the input as a graph: nodes are states (positions, strings, board configurations) and edges are valid moves between them. Starting from a source node, it enqueues that node, then repeatedly:

1. Dequeues the front of the queue.
2. Generates all neighboring states.
3. Enqueues any neighbor that has not been visited yet.
4. Marks each enqueued neighbor as visited.

Because the queue processes nodes in the order they were discovered, all nodes at distance d from the start are processed before any node at distance d+1. That ordering is what gives BFS its optimal‑step guarantee.

Signals That Call for BFS

If the problem mentions weights or costs that differ between edges, Dijkstra’s algorithm (or A*) is usually the right tool, not plain BFS.

Worked Example: Word Ladder

Problem statement (paraphrased): Given a start word, an end word, and a dictionary of allowed words, find the length of the shortest transformation sequence where each step changes exactly one letter and the intermediate word must be in the dictionary.

Step‑by‑Step Solution

1. Model the graph – each word is a node; an edge exists between two words if they differ by one character.
2. Queue – store tuples (current_word, steps_so_far).
3. Visited set – prevents revisiting the same word.
4. Termination – when we dequeue the target word, the associated step count is the answer.

from collections import deque

def ladder_length(begin: str, end: str, word_list: set) -> int:
    if end not in word_list:
        return 0
    queue = deque([(begin, 1)])  # (word, depth)
    visited = {begin}
    while queue:
        word, depth = queue.popleft()
        if word == end:
            return depth
        # generate neighbors by changing each position
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nxt = word[:i] + c + word[i+1:]
                if nxt in word_list and nxt not in visited:
                    visited.add(nxt)
                    queue.append((nxt, depth + 1))
    return 0

Complexity – Each word is processed once, and generating neighbors costs O(26 * L) where L is word length. Overall time is O(N * L * 26) and space is O(N) for the visited set and queue.

Common Pitfalls

• Marking visited too late – If you add a neighbor to the queue before checking visited, you may enqueue the same state multiple times, blowing up memory.
• Mutating the queue element – Storing mutable objects (e.g., a list that you later modify) can corrupt earlier states.
• Forgetting termination condition – In some problems the target may be unreachable; you must return a sentinel (often -1 or 0).
• Assuming weighted edges – BFS works only when each edge has equal cost. If the problem mentions "cost" or "time" per move, reconsider the algorithm.

Five Practice Problems

Below are five problems that exercise different aspects of BFS. They are described in your own words; you should write the full solution yourself.

1. Minimum Knight Moves

Prompt: On an infinite chessboard, a knight starts at (0,0). Find the minimum number of moves to reach a target square (x, y).

Hint: Treat each board position as a node; the eight possible knight jumps are edges. Use symmetry to limit the search space (e.g., work only in the first quadrant). BFS guarantees the shortest move count.

2. Escape from a Maze

Prompt: You are given a 2‑D grid of '0' (open) and '1' (wall). You can move up, down, left, or right. Starting at the top‑left cell, find the minimum number of steps to reach the bottom‑right cell.

Hint: Classic grid BFS. Enqueue coordinates with a step counter. Mark cells as visited when you enqueue them to avoid revisiting.

3. Number of Islands – Shortest Bridge

Prompt: Two islands of '1' cells exist in a binary matrix. Flip the fewest '0' cells to '1' to connect the islands. Return that minimum number.

Hint: First BFS from one island to label its cells. Then start a second BFS that expands outward from the first island, counting layers until you hit the second island.

4. Word Break – Minimum Segments

Prompt: Given a string s and a dictionary wordDict, find the minimum number of words needed to segment s completely. Return -1 if impossible.

Hint: Model each index as a node; an edge from i to j exists if s[i:j] is a dictionary word. BFS from index 0 finds the shortest path to len(s).

5. Minimum Number of Coins (Unweighted)

Prompt: You have an unlimited supply of coin denominations [c1, c2, …]. Find the fewest coins needed to make amount A. Assume all denominations are positive integers.

Hint: Treat each amount from 0 to A as a node. An edge adds a coin value. BFS from 0 reaches A in the smallest number of steps, i.e., the minimal coin count.

How to Practice This

1. Write the BFS skeleton – start each problem by drafting the queue, visited set, and loop structure before thinking about neighbor generation.
2. Validate with small examples – manually trace the first two layers on paper to ensure you are marking visited at the right time.
3. Use Call Assistant for mock interviews – run through a problem aloud, let the assistant capture your reasoning, and rehearse answering follow‑up “what if …” questions while staying grounded in your own solution.

FAQ

• When should I prefer DFS over BFS? Use DFS when you need to explore all possible paths (e.g., generating permutations) or when the problem asks for any solution rather than the shortest one.

• Can BFS handle very large graphs? It works as long as the frontier fits in memory. For massive graphs, you may need bidirectional BFS or a heuristic search like A*.

• What if the graph is weighted but all weights are the same integer? Plain BFS still works because each edge contributes the same cost; you can treat the weight as an extra step count.

• How do I avoid TLE on LeetCode‑style problems? Optimize neighbor generation (e.g., pre‑compute possible transformations) and prune early by checking goal conditions before enqueuing.