Shortest Path in Binary Matrix

Table of Contents +

Shortest Path in Binary Matrix is a grid version of the shortest-path idea. The twist that trips people up is movement. Here you can step in eight directions, not just four. The interviewer wants to see that you spot a grid as a graph and pick BFS for the shortest path.

🎯 The Problem

You walk across a square grid of open and blocked cells, looking for the shortest clear path.

The grid holds 0 and 1. A 0 is an open cell you can stand on. A 1 is blocked.
You start at the top-left corner and want to reach the bottom-right corner.
You may move to any of the eight neighbors. That is up, down, left, right, and the four diagonals.
Every step costs one.
Return the number of cells on the shortest clear path, counting both ends.
If no clear path exists, return -1.

Let us take a small grid. The top-left and bottom-right must both be 0, or there is no path at all.

Input:
  0 0 0
  1 1 0
  1 1 0
Output: 4

Explanation: One shortest clear path is
(0,0) -> (0,1) -> (1,2) -> (2,2), which is 4 cells.

Think of each open cell as a node, which is a point in a graph. An edge joins two open cells that are neighbors in any of the eight directions. So the grid is just a graph drawn as a square.

🐢 Approach 1: Depth-First Search (Brute Force)

We try every route and keep the shortest.

The idea:

Follow one route as far as it goes, then back up and try another.
This is a depth-first search. It goes deep down one path before trying others.

How it works:

Track visited cells, or the walk loops forever.
Record the length of every full route to the end. Keep the smallest.

Why it is weak:

It explores long routes before short ones.
On a grid the number of routes explodes.
Far too slow and wasteful here.

Here is the DFS path search:

def shortest_path_binary_matrix(grid):
    n, best = len(grid), float("inf")
    def dfs(r, c, dist, seen):
        nonlocal best
        if r < 0 or c < 0 or r == n or c == n or grid[r][c] or (r, c) in seen or dist >= best: return
        if r == n - 1 and c == n - 1:
            best = min(best, dist); return
        seen.add((r, c))
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr or dc: dfs(r+dr, c+dc, dist+1, seen)
        seen.remove((r, c))
    dfs(0, 0, 1, set())
    return -1 if best == float("inf") else best

⚡ Approach 2: Breadth-First Search With 8 Directions (Best)

The idea in one line: spread out in rings from the start, so the first time you touch the end is the shortest path.

The idea:

Breadth-first search, or BFS, explores the grid in rings around the start.
First all cells one step away. Then all cells two steps away. And so on.
Every step costs the same, so the first time BFS reaches the end it came by the shortest path.

How it works:

Drive BFS with a queue. A queue serves items first in, first out, like a line at a shop.
Push the start cell with distance one.
Pop a cell, look at its eight neighbors, push each open unvisited neighbor with distance plus one.
Keep a neighbor only if it is inside the grid, a 0, and not visited.
Mark a cell visited the moment you push it, so it never enters the queue twice.
Guard up front: if the start or end cell is a 1, return -1 at once.

Why it is fast:

Each cell enters the queue at most once.
The eight neighbor checks per cell are a constant amount of work.

Here is BFS spreading out in rings from the start. Each ring is one more step away. The end cell is reached on ring four.

Steps to Solve

If the start or the end cell is blocked, return -1.
Create a queue and push the start cell with distance 1. Mark it visited.
Pop a cell. If it is the end cell, return its distance.
Build all eight neighbors using the row and column offsets.
For each neighbor, keep it only if it is inside the grid, open, and not visited.
Mark each kept neighbor visited and push it with distance plus one.
If the queue empties without reaching the end, return -1.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a deque for the queue and a set of visited cells.

from collections import deque


def shortest_path(grid):
    n = len(grid)
    if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:   # blocked ends
        return -1

    directions = [(-1, -1), (-1, 0), (-1, 1),
                  (0, -1),           (0, 1),
                  (1, -1),  (1, 0),  (1, 1)]         # 8 moves

    queue = deque([(0, 0, 1)])      # each item is (row, col, distance)
    visited = {(0, 0)}

    while queue:
        r, c, d = queue.popleft()
        if r == n - 1 and c == n - 1:    # reached the end cell
            return d

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n \
               and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))    # mark before pushing
                queue.append((nr, nc, d + 1))
    return -1                       # no clear path


grid = [[0, 0, 0],
        [1, 1, 0],
        [1, 1, 0]]
print(shortest_path(grid))

The output of the above code will be:

Let us walk through the Python version line by line. Code first, then the why.

We start with n = len(grid), the side length. Then the guard if grid[0][0] != 0 or grid[n-1][n-1] != 0: return -1. If either end is blocked there is no path, so we stop right away.

directions lists the eight moves as row and column changes. Up-left is (-1, -1). Right is (0, 1). And so on for all eight. Holding them in one list lets us loop over every neighbor with no copy-paste.

queue = deque([(0, 0, 1)]) seeds the BFS at the start cell with distance one. The distance counts cells on the path so far. The start alone is a path of one cell. visited = {(0, 0)} marks the start so we never return to it.

The loop while queue: runs until we run out of cells. r, c, d = queue.popleft() takes the oldest cell first. That front-first order is what makes this BFS, so closer cells finish before farther ones.

if r == n-1 and c == n-1: return d is the win. The first time we pop the end cell, its distance is the shortest path length. BFS guarantees that on an equal-cost grid.

The neighbor loop is the core. for dr, dc in directions walks all eight moves. nr, nc = r + dr, c + dc is the neighbor cell. The check keeps it only if it is inside the grid, open with value 0, and not visited. We visited.add((nr, nc)) before pushing. Marking on push, not on pop, stops the same cell from entering the queue twice. Then queue.append((nr, nc, d + 1)) adds the neighbor one step farther out.

⏱️ Time and Space Complexity

Let the grid be n by n, so it has n² cells. BFS visits each cell at most once. For each cell it checks eight neighbors, which is a constant. So the time is O(n²). The queue and the visited set each hold at most n² cells, so the space is O(n²) too.

Approach	Time Complexity	Space Complexity
Depth-first search (brute force)	Exponential	O(n²)
Breadth-first search with 8 directions	O(n²)	O(n²)

Tip

The two things that catch people are the eight directions, not four, and the early guard when an end cell is blocked. Say both out loud and your interviewer will know you have done grid BFS before.

🧩 Key Takeaways

✅ A grid is a graph. Each open cell is a node and neighbors are edges.
✅ BFS explores in rings, so the first time it reaches the end is the shortest path.
✅ Here you move in eight directions, including the four diagonals.
✅ Check each neighbor for inside the grid, open, and not visited before pushing.
✅ Mark a cell visited when you push it, so it never enters the queue twice.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Word Ladder
Accounts Merge

Previous Accounts Merge Next Making a Large Island

Shortest Path in Binary Matrix

Follow Us

Follow Us