Skip to main content
DSA patterns

Shortest Path in Binary Matrix

mediumGraphsGoogleAWSAzure

Problem statement

You are given an n × n grid of 0s and 1s. A 0 is an open cell and a 1 is blocked. Find the shortest path from the top-left cell to the bottom-right cell that uses only open cells. From any cell you may move to any of its 8 neighbours — up, down, left, right, or diagonally.

The length of a path is the number of cells on it, including the first and the last. Return that length, or -1 if no such path exists.

Think of it as routing through a data-centre floor where some tiles are blocked: what is the fewest number of tiles a cable run has to cross?

Examples

Example 1

Input: grid = [[0,1],[1,0]]

Output: 2

Explanation: The two open cells touch diagonally, so the path is just the start and the end: 2 cells.

Example 1

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Explanation: Go right along the top row to (0,1), step diagonally to (1,2), then down to (2,2). That visits 4 cells, and no shorter route exists because the middle and bottom-left are blocked.

Example 2

Example 3

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]

Output: -1

Explanation: The start cell itself is blocked, so no path can begin.

Hints

Hint 1: Every step has the same cost (one cell). Which search finds the fewest steps when every step costs the same?

Approach

Optimal: BFS

Intuition

When every step costs the same, breadth-first search (BFS) finds the shortest path. BFS uses a queue (first in, first out) and explores in rings: first every cell 1 step from the start, then every cell 2 steps away, and so on. So the first time it reaches a cell, it has used the fewest steps possible to get there — and when it reaches the goal, that distance is the answer.

This is why DFS was the wrong tool: DFS dives down one path and has to try all of them, while BFS reaches every cell by its shortest route the first time. Record each cell's distance when you first add it to the queue; a cell that already has a distance is never added again.

Steps

  1. If the start or the end cell is 1, return -1.
  2. Create dist, an n × n grid of 0 ("not reached yet"). Set dist[0][0] = 1 and put (0, 0) in a queue.
  3. While the queue isn't empty:
    • Take out (r, c). If it is the goal, return dist[r][c].
    • For each of the 8 neighbours inside the grid that is open and has dist == 0: set its dist to dist[r][c] + 1 and add it to the queue.
  4. If the queue empties without reaching the goal, return -1.

Dry run

Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]

take distance newly reached (distance)
(0,0) 1 (0,1) → 2
(0,1) 2 (0,2) → 3, (1,2) → 3
(0,2) 3 none new
(1,2) 3 (2,2) → 4
(2,2) 4 goal → return 4

Edge cases: in Example 3 the start is blocked, so the answer is -1 before the search starts. A 1 × 1 grid with a 0 returns 1, because the start is already the goal.

Complexity

Time O(n²) - Each cell enters the queue at most once, because it is given a distance the first time it is reached. Taking a cell out checks its 8 neighbours, which is constant work. So the search does a fixed amount of work per cell. For the largest 100 × 100 grid that is at most 10,000 cells and 80,000 neighbour checks.

Space O(n²) - The distance grid holds one number per cell, and the queue can hold up to n² cells in the worst case. The input grid is left unchanged.

from collections import deque
from typing import List


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1
        dist = [[0] * n for _ in range(n)]
        dist[0][0] = 1
        queue = deque([(0, 0)])
        while queue:
            r, c = queue.popleft()
            if r == n - 1 and c == n - 1:
                return dist[r][c]
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and dist[nr][nc] == 0:
                        dist[nr][nc] = dist[r][c] + 1
                        queue.append((nr, nc))
        return -1


if __name__ == "__main__":
    print(Solution().shortestPathBinaryMatrix([[0, 1], [1, 0]]))  # 2
    print(Solution().shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]))  # 4
    print(Solution().shortestPathBinaryMatrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]]))  # -1
RecapThe whole problem in a few lines, for the night before
  • Spot it: "shortest path" or "fewest steps" through a grid with blocked cells — uniform cost per move
  • Idea: BFS explores in order of distance, so the first time you dequeue the destination you have the shortest length; check all 8 neighbors, not just 4
  • Cost: O(n²) time and space — each of the n² cells is visited and enqueued at most once
  • Trap: forgetting the four diagonal neighbors, or marking a cell visited on dequeue instead of on enqueue (which lets it be queued multiple times)

Interview follow-ups

  • Return the path itself, not just its length.

    Store a parent for each cell when you first reach it. When BFS reaches the goal, follow the parents back to the start and reverse the list. Time and space stay O(n²). In routing terms, that list is the actual sequence of hops a packet should take.

  • Moves are only up, down, left and right. What changes?

    Only the list of neighbours: use 4 directions instead of 8. The BFS, the distance grid and the O(n²) cost are unchanged. Answers usually get longer, since diagonal shortcuts are gone.

  • Some cells are slow to cross (cost 2 or 5) instead of open or blocked. How do you find the cheapest path?

    BFS no longer works, because a path with more cells can now be cheaper. Use Dijkstra's algorithm: a priority queue always expands the cell with the lowest total cost so far. On an n × n grid that costs O(n² log n). If costs are only 0 or 1, a simpler "0-1 BFS" with a double-ended queue does it in O(n²).

Frequently asked questions

DFS follows one path as deep as it can, so the first time it reaches the goal it may have taken a long detour; to be sure, it must try every path. BFS reaches cells in order of distance, so its first arrival at the goal is guaranteed to be the shortest. That guarantee holds whenever every step costs the same, which is the case here.

Looping dr and dc over -1, 0, 1 gives 9 pairs, including (0, 0) — the cell itself. It is harmless: the current cell already has a distance, so the dist == 0 check skips it. Writing the two small loops is shorter and less error-prone than listing all 8 directions by hand.

If either is blocked, no path can exist, and the answer is -1 immediately. Without the check, a blocked start would still be put in the queue and treated as open, which gives a wrong answer. The end check isn't strictly needed for correctness, but it saves a full search.

Dijkstra's algorithm is for paths where steps have different costs; with equal costs it does the same thing as BFS, just slower because of its priority queue. A* adds a guess of the remaining distance to steer the search toward the goal, which can visit fewer cells on big open maps. For this problem BFS is the expected answer, and mentioning A* as an optimisation is a bonus.

"Fewest hops from A to B" is the core of routing: the minimum number of network hops between two hosts, or the fewest services a request passes through. When every hop costs the same, the answer is a BFS. The grid version tests that you pick BFS, handle blocked cells, and remember the diagonal moves.