Shortest Path in Binary Matrix: Why BFS Works & Common Mistakes

What the Interviewer Is Really Testing#

When an interviewer hands you the Shortest Path in Binary Matrix problem, they're not just checking if you can Google "BFS." They want to see if you understand why BFS is the right tool — and more importantly, whether you can articulate that reasoning out loud under pressure.

Here's what a strong answer signals to your interviewer:

You recognize this as a shortest path problem in an unweighted graph
You know BFS guarantees the shortest path at first reach — and you can explain why
You handle edge cases without being prompted
You write clean, correct code the first time

A weak answer? Jumping straight into DFS, getting a path, and saying "I'll optimize later." That's a red flag. Let's make sure you don't go there.

The Problem, Clearly Stated#

You're given an n x n binary grid where:

0 → open cell (you can walk here)
1 → blocked cell (you cannot)

Find the shortest path from (0, 0) to (n-1, n-1) where:

You can only walk on 0s
You can move in 8 directions (up, down, left, right, and all 4 diagonals)
Return the number of cells in the shortest path
If no path exists, return -1

Simple enough on the surface. But this problem has more traps than most candidates expect.

Why BFS — The Core Intuition#

Let's talk about the insight that separates good answers from great ones.

This is a shortest path problem on an unweighted graph. Every move costs exactly 1 step. That single fact tells you everything: reach for BFS (Breadth-First Search).

Here's the thing most people miss about BFS — it's not just a traversal technique. It's a shortest path algorithm. The reason it works comes down to one key property:

The first time BFS reaches a node, it is guaranteed to be via the shortest path.

Why? Think of BFS like a wave spreading outward from your starting point:

Wave 1 → all cells exactly 1 step from (0,0)
Wave 2 → all cells exactly 2 steps from (0,0)
Wave 3 → all cells exactly 3 steps from (0,0)
...

BFS never skips a wave. It explores all shorter paths before touching any longer ones. So the moment (n-1, n-1) appears in the queue, you know for certain: every path of smaller length has already been explored, and none of them reached the destination. This one — the path you just found — is the shortest.

This is the explanation your interviewer wants to hear. Don't just say "BFS finds the shortest path." Explain the wave analogy. That's what separates a candidate who memorized an answer from one who actually understands it.

Why DFS Fails Here#

A common trap: candidates reach for DFS because it feels familiar. DFS goes deep first, which means it might find a path of length 10 even when a path of length 3 exists. There's no mechanism in DFS that guarantees you've found the shortest path — only a path.

Algorithm	Finds a path?	Finds the shortest path?
DFS	✅ Yes	❌ Not guaranteed
BFS	✅ Yes	✅ Always (unweighted)
Dijkstra	✅ Yes	✅ Yes (weighted)

BFS works here because all edges have equal cost. If the grid had varying movement costs, you'd need Dijkstra's algorithm. But here? BFS is perfect and more efficient.

The Solution: Walking Through the Code#

Let's build this together, step by step.

python

from collections import deque
 
def shortestPathBinaryMatrix(grid):
    n = len(grid)
 
    # Edge case: start or end is blocked
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
 
    # Special case: single cell grid
    if n == 1:
        return 1
 
    # BFS setup
    queue = deque()
    queue.append((0, 0, 1))  # (row, col, path_length)

A few things to call out here that interviewers specifically look for:

Edge case handling upfront — check if start/end is blocked before doing anything else
Mark visited when enqueuing, not when dequeuing — more on this in the mistakes section
Path length is cell count, not edge count — we start at 1 because (0,0) itself is the first cell
All 8 directions — not just 4

Where Candidates Get Stuck#

I've watched hundreds of candidates attempt this problem. Here are the most common places they trip up — and how to recover.

Mistake #1: Using DFS#

This happens when someone panics and grabs the first graph traversal they remember. If you catch yourself starting a DFS, pause and ask: "Does this problem need the shortest path?" Yes? Then BFS. Always.

Mistake #2: Forgetting Diagonal Directions#

Candidates who solve a lot of grid problems default to 4-directional movement. This problem explicitly allows 8. Double-check the problem statement. In an interview, say out loud: "This problem allows diagonal movement, so I'll use all 8 directions."

Mistake #3: Marking Visited Too Late#

This is subtle but critical. Here's what happens if you mark a cell as visited after you dequeue it (wrong approach):

python

# ❌ WRONG — marks visited after dequeuing
while queue:
    row, col, path_len = queue.popleft()
    grid[row][col] = 1  # Too late!
    for dr, dc in directions:
        nr, nc = row + dr, col + dc
        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
            queue.append((nr, nc, path_len + 1))

The problem? Multiple neighbors can all add the same unvisited cell to the queue before any of them get processed. That cell gets explored multiple times, your queue balloons in size, and you hit TLE (Time Limit Exceeded) on large inputs.

python

# ✅ CORRECT — marks visited when enqueuing
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
    grid[nr][nc] = 1  # Mark it here
    queue.append((nr, nc, path_len + 1))

Mark visited the moment you add a cell to the queue. This guarantees each cell is processed exactly once.

Mistake #4: Wrong Path Length Definition#

Path length here is the number of cells visited, not the number of edges. For a single-cell grid [[0]], the answer is 1, not 0. Start your counter at 1 and increment with each step.

Mistake #5: The "Early Exit" Misconception#

This one is subtle, and it trips up candidates who think they understand BFS but don't quite have the intuition locked in.

❌ "We return early when we find the destination, so that's why it's the shortest path."

✅ "We return when we first reach the destination because BFS guarantees that the first time we reach any node is via the shortest path. The early return is a consequence of that guarantee, not the reason for it."

If an interviewer pushes back and asks "but how do you know it's the shortest?", you need that second explanation ready. The first answer will not satisfy a senior interviewer.

How to Talk Through This in an Interview#

Here's a sample walkthrough of how I'd coach you to narrate this problem out loud. Talking through your thought process is just as important as the code itself.

Step 1 — Clarify and restate:

"So I'm finding the shortest path from the top-left to the bottom-right corner of a binary grid, moving on zeros in 8 directions, and I return the cell count. Let me make sure I have that right before diving in."

Step 2 — Identify the algorithm:

"This is a shortest path problem on an unweighted graph — each move costs exactly 1 step. That tells me BFS is the right approach. BFS explores nodes level by level, so the first time it reaches the destination is guaranteed to be via the shortest path."

Step 3 — Walk through edge cases before coding:

"A few edge cases I want to handle upfront: if the start or end cell is blocked, we immediately return -1. And if the grid is 1x1 and the cell is open, the answer is 1."

Step 4 — Code, narrating as you go:

"I'll initialize my queue with the starting position and path length 1. I'm marking cells as visited when I add them to the queue — not when I dequeue — to avoid processing the same cell multiple times. I'll check all 8 directions at each step..."

Step 5 — Wrap up with complexity:

"Time complexity is O(n²) since each cell is visited at most once. Space is also O(n²) for the queue in the worst case."

Follow-Up Questions to Prepare For#

A good interviewer won't stop when you write the solution. Here's what's coming next — and how to handle it:

"What if the grid had weighted edges?" BFS no longer works because it assumes all edges are equal. You'd switch to Dijkstra's algorithm with a min-heap. Say that confidently.

"What if you couldn't modify the grid to mark visited cells?" Use a separate visited set. visited.add((row, col)) before enqueuing.

"Can you do this without BFS?" You could use Dijkstra's (it reduces to BFS when all weights are 1), or A* with a heuristic for optimization. But plain BFS is the optimal solution here.

"Why not bidirectional BFS?" Great question if they bring it up — bidirectional BFS searches from both start and end simultaneously, which can cut the search space roughly in half. It's an optimization, not a requirement here. Show you know it exists.

Complexity Analysis#

	Complexity
Time	O(n²) — each of the n² cells is visited at most once
Space	O(n²) — queue can hold up to n² cells in the worst case

Be ready to justify these. The interviewer may ask: "Could there be more than n² operations?" No — because each cell is marked visited before being added to the queue a second time. So total operations are bounded by the grid size.

Red Flags to Avoid#

Starting to code without clarifying — always restate the problem and check edge cases first
Choosing DFS without justification — if you go DFS, you better have a reason
Forgetting to mark visited — this will cause TLE and shows you haven't thought through correctness
Saying "BFS is shortest" without explaining why — interviewers want the reasoning, not just the conclusion
Ignoring the single-cell edge case — [[0]] returning 1 trips up a surprising number of candidates
Hardcoding 4 directions — always re-read whether the problem is 4-directional or 8-directional

Key Takeaways#

Here's what to carry into your interview:

BFS is the right algorithm for shortest path in unweighted grids — if all moves cost the same, reach for BFS first
The golden rule: the first time BFS reaches a node is always via the shortest path — be able to explain the wave analogy
Mark cells as visited when enqueuing, not when dequeuing — this prevents duplicate processing and TLE
Path length = number of cells, not edges — start at 1, not 0
Always handle blocked start/end as an edge case — check grid[0][0] and grid[n-1][n-1] before anything else
Don't mistake early exit for the reason BFS gives shortest path — the guarantee comes from BFS's level-by-level exploration
If weights were unequal, you'd need Dijkstra's — knowing when BFS breaks shows real depth of understanding

Nail the explanation, not just the code. That's what gets you the offer.