I Knew BFS Existed but Couldn't Wire It Into a Grid Problem

I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.

The problem

LeetCode 1091: Shortest Path in Binary Matrix. You get an n×n grid of 0s and 1s. Find the shortest path from the top-left corner to the bottom-right corner, moving through cells with value 0. You can move in all 8 directions (up, down, left, right, and all four diagonals). Return the number of cells in the path, or -1 if no path exists.

I looked at this and thought: okay, at every cell that's a 0, I check the connected neighbors. Skip anything out of bounds or already visited. Straightforward enough.

But when I actually sat down to write it, two things tripped me up. I didn't know how to pick BFS over DFS for this. And even after choosing BFS, I had no idea how to track the path length.

"Shortest" is doing the work

My first instinct was just "explore the neighbors." I hadn't committed to BFS or DFS. Both would find a path. But the problem says shortest, and that word changes everything.

DFS goes deep. It picks one direction and follows it as far as possible before backtracking. It'll find a path, but it might be a terrible one. To guarantee the shortest, you'd have to explore every possible path and compare. That's expensive.

BFS explores in waves. Wave 1 is everything 1 step from the start. Wave 2 is everything 2 steps away. Wave 3, everything 3 steps. The first time you reach the destination, you got there in the fewest steps possible. You never need to compare alternatives because you tried all shorter routes first.

That's the core insight: BFS gives you shortest path for free. You don't need extra logic to compare paths or track the minimum. The structure of the algorithm handles it.

"How do I track the distance though?"

This was my actual sticking point. I had a queue. I was popping cells and pushing neighbors. The BFS loop worked. But I couldn't figure out where the path length came from.

My queue held coordinates like [i, j]. When I reached the bottom-right corner, I had no way to know how many steps it took to get there.

The fix is simple once you see it: store the distance with each item in the queue. Instead of [i, j], push [i, j, distance]. The start cell goes in as [0, 0, 1] (distance 1 because the problem counts the start cell). When you process a cell at distance d and add its neighbors, each neighbor gets d + 1. When you pop the destination cell, its distance is your answer.

queue.append([0, 0, 1])  # row, col, distance

# later, when adding neighbors:
queue.append([ni, nj, curr_distance + 1])

That's it. The distance piggybacks on the BFS traversal. No separate tracking needed.

The full solution

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0:
            return -1

        n = len(grid)
        queue = deque()
        queue.append([0, 0, 1])
        grid[0][0] = -1  # mark visited

        while len(queue) > 0:
            curr = queue.popleft()
            i, j, dist = curr[0], curr[1], curr[2]

            if i == n - 1 and j == n - 1:
                return dist

            for di in [-1, 0, 1]:
                for dj in [-1, 0, 1]:
                    if di == 0 and dj == 0:
                        continue
                    ni, nj = i + di, j + dj
                    if ni >= 0 and ni < n and nj >= 0 and nj < n:
                        if grid[ni][nj] == 0:
                            queue.append([ni, nj, dist + 1])
                            grid[ni][nj] = -1

        return -1

Walk through a small grid to see the waves:

[0, 0, 1]
[0, 1, 0]
[0, 0, 0]

Wave 1 (distance 1): (0,0).
Wave 2 (distance 2): (0,1), (1,0).
Wave 3 (distance 3): (2,0), (2,1).
Wave 4 (distance 4): (2,2), (1,2).

BFS reaches (2,2) at distance 4. That's the answer.

Mistakes I made that are probably common

Counting edges instead of cells. I initially set the starting distance to 0. For the grid above, that gives 3 instead of 4. The LeetCode problem counts cells visited (both endpoints), not hops between them. This is the kind of off-by-one that makes you fail test cases and stare at correct-looking code for ten minutes.

Marking cells as visited when popping, not when enqueueing. This is subtle. Say cell (1,1) is a neighbor of both (0,0) and (0,1). If you process (0,0) first and add (1,1) to the queue but don't mark it visited yet, then when you process (0,1), you add (1,1) again. Now it's in the queue twice, and all its neighbors get processed twice too. The fix: mark a cell visited the moment you add it to the queue, not when you pop it.

Off-by-one on the destination check. If the grid is 5×5, the bottom-right is (4,4), not (5,5). Checking i == len(grid) instead of i == len(grid) - 1 means you never find the destination. Obvious in hindsight. Not obvious at 11pm.

Using list.pop(0) instead of collections.deque. A regular Python list pops from the front in O(n) because it shifts every remaining element. On a big grid, this quietly turns your O(n) BFS into O(n²). deque.popleft() is O(1). Small change, big difference.

When BFS works (and when it doesn't)

BFS gives shortest path when all edges have the same weight. In a grid where every step costs 1, that holds. If some steps cost more than others (weighted graph), BFS won't work. You'd need Dijkstra's algorithm instead.

The BFS template itself stays remarkably stable across problems. Once you have the loop, the only things that change are:

Where you start. One cell? Multiple cells at once? Every cell of a certain type? (Multi-source BFS seeds the queue with all starting points at distance 0.)

Where you stop. Reached a specific cell? All targets converted? Queue is empty?

Which directions. 4-directional (up/down/left/right) or 8-directional (including diagonals)?

The loop, the queue, the visited tracking, the distance propagation: all identical every time.

Practice problems

In order of difficulty, all using BFS on grids:

1. LeetCode 994 (Rotting Oranges): Multi-source BFS. All rotten oranges start spreading simultaneously. Same wave-by-wave expansion, but you seed the queue with every rotten cell instead of one corner.
2. LeetCode 542 (01 Matrix): Find the shortest distance from every cell to the nearest 0. Multi-source BFS starting from all 0-cells.
3. LeetCode 1162 (As Far from Land as Possible): Multi-source BFS from all land cells. The answer is the last wave number. Same pattern, different framing.
4. LeetCode 752 (Open the Lock): BFS on a non-grid graph. Each "node" is a 4-digit lock combination. Neighbors are one-digit turns. Tests whether you see that BFS works on any graph, not just grids.
5. LeetCode 127 (Word Ladder): BFS on words where neighbors differ by one letter. Harder to see the graph structure, but the BFS mechanics are identical.