Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Shortest Path in a Binary Matrix

Shortest path in a binary matrix explained: BFS finds the fewest steps in an unweighted grid with 8-way moves. Tested Python, edge cases and a live visual.

Also searched as: shortest path in a grid with 8 directions · BFS shortest path in a maze

🏝️

Try it live Free

Number of Islands & Grid BFS

Draw a maze in the Grid BFS lab and race BFS against DFS from S to T: BFS reaches T by a shortest route, DFS often by a longer one.

Also useful: Graph Search: BFS vs DFS, Dijkstra's Shortest Path

Open the playground →

The problem

Given an n x n grid of 0s (open) and 1s (blocked), find the length of the shortest path from the top-left to the bottom-right cell, moving through open cells in any of the 8 directions. The length counts cells on the path. Return -1 if there is no path.

Inputgrid = [[0,1],[1,0]]
Output2

Move diagonally.

Inputgrid = [[1,0,0],[1,1,0],[1,1,0]]
Output-1

The start is blocked.

The key insight

Every move costs the same, so this is an unweighted shortest path, and BFS is the right tool: it explores cells in order of distance, so the first time it reaches the target is along a shortest path. DFS can find a path, but not necessarily the shortest one.

Brute force first: Trying every path with DFS and keeping the minimum is exponential in the grid size.

Step-by-step approach

  1. If the start or the end cell is blocked, return -1.
  2. Push (0, 0) with distance 1 and mark it visited.
  3. Pop a cell; if it is the bottom-right, return its distance.
  4. Otherwise push every in-bounds, open, unvisited neighbour among the 8 directions with distance + 1, marking it visited as you push.
  5. If the queue empties first, return -1.

Python solution

PYTHON 3tested
from collections import deque


def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    seen = {(0, 0)}
    q = deque([(0, 0, 1)])             # row, col, path length in cells
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n - 1, n - 1):
            return d
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not grid[nr][nc] and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Complexity

TimeO(n²)
SpaceO(n²)

There are n² cells; each is enqueued once and checks 8 neighbours, which is a constant. The visited set and queue hold up to n² cells.

Common mistakes

Frequently asked questions

What is the time and space complexity of shortest path in a binary matrix?

O(n²) time for an n by n grid, since each cell is processed once with 8 neighbour checks, and O(n²) space for the visited set and queue.

Why does BFS find the shortest path and DFS does not?

BFS processes cells in increasing distance from the start, so the first arrival at the target is along a shortest path. DFS follows one branch deeply and may reach the target by a long detour first.

What if moves had different costs?

Then BFS no longer guarantees the shortest path. Use Dijkstra's algorithm with a priority queue, or 0-1 BFS with a deque when costs are only 0 or 1.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.