DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Shortest Path in Binary Matrix

mediumGraphs Must-do

Problem statement

You're given an n x n grid where every cell is 0 (clear) or 1 (blocked). Starting at the top-left cell and ending at the bottom-right cell, find the length of the shortest path that only steps through 0 cells. From any cell you can move to any of its 8 neighbors — up, down, left, right, and the four diagonals. The length of a path is the number of cells it visits, including the start and end. If no such path exists, return -1.

Picture the grid as a map of nodes in a small mesh network, where 1 marks a node that's down. You're looking for the fewest hops to get a message from one corner of the mesh to the other, allowed to hop to any of the 8 neighbors a node has on the grid.

Examples

Example 1

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

Output: 2

Explanation: The only clear cells are the start (0,0) and the end (1,1), and they're diagonally adjacent, so the path is just those two cells.

Example 1

Example 2

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

Output: 4

Explanation: The path (0,0) → (0,1) → (0,2) → (1,2) → (2,2) has 5 cells, but a shorter one exists: (0,0) → (0,1) → (1,2) → (2,2) moves diagonally from (0,1) to (1,2), visiting only 4 cells.

Example 2

Example 3

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

Output: -1

Explanation: The start cell (0,0) is 1 — blocked — so no path can even begin.

Hints

Approach

Optimal: BFS reusing the grid as the visited marker

Intuition

The Better approach needs a whole second n x n grid just to track which cells have been visited. But the input grid already tells us which cells are "available" — a 0 — and once we've queued a cell, we don't need it to stay a 0 anymore. So instead of a separate visited grid, overwrite each cell with 1 (blocked) the moment it's enqueued. This reuses memory the input already occupies instead of allocating a fresh grid, which matters if n is large and memory is tight — the same trade a service makes when it marks a work item "claimed" in place rather than keeping a side table of claimed IDs.

Process the queue level by level — everything at the current distance before moving to the next — so a shared length counter can be incremented once per level instead of being carried inside every queue entry.

Steps

  1. If the start or end cell is blocked, return -1.
  2. Push (0, 0) onto the queue and immediately set grid[0][0] = 1 to mark it used. Start length at 1.
  3. While the queue isn't empty:
    • Process every cell currently in the queue (one full level):
      • Dequeue (r, c). If it's the destination, return length.
      • For each of its 8 neighbors that's in bounds and still 0, set it to 1 and enqueue it.
    • After the whole level is processed, increment length.
  4. Return -1 if the queue empties without reaching the destination.

Dry run

grid = [[0,0,0],[1,1,0],[1,1,0]]

level length cells processed newly marked
1 1 (0,0) (0,1)
2 2 (0,1) (0,2), (1,2)
3 3 (0,2), (1,2) (2,2)
4 4 (2,2) → destination, return 4 —

Edge cases: same as Better — a 1x1 clear grid returns 1, and a fully boxed-in start returns -1 once the queue drains. Mutating the input grid is safe here because the page's main only calls the function once per example; a caller who needs the original grid preserved should pass a copy.

Complexity

Time O(n²)

Space O(1) — extra, beyond the input and the queue

from collections import deque

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

        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
                      (0, 1), (1, -1), (1, 0), (1, 1)]
        q = deque([(0, 0)])
        grid[0][0] = 1
        length = 1

        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                if r == n - 1 and c == n - 1:
                    return length
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        q.append((nr, nc))
            length += 1
        return -1


if __name__ == "__main__":
    print(Solution().shortestPathBinaryMatrix([[0, 1], [1, 0]]))
    print(Solution().shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]))
    print(Solution().shortestPathBinaryMatrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]]))

Follow-up questions

Represent only the clear cells — for example, a set of (row, col) pairs, or a sparse adjacency structure built by scanning the grid once up front. BFS then only ever touches actual clear cells and their clear neighbors, so the cost tracks the number of clear cells rather than the full n² grid. This helps most when the grid is sparse; a mostly-clear grid gains little from it.

Once edges have different costs, BFS no longer guarantees the shortest path — you need Dijkstra's algorithm with a min-heap, tracking the cheapest known cost to reach each cell instead of just its distance in hops. The 8-direction neighbor logic stays the same; only the "explore in order of distance" step changes to "explore in order of cheapest total cost so far."

Alongside the visited marker, store a parent map (or a parent grid) recording which cell enqueued each new cell. Once the destination is dequeued, walk backward through parent from the destination to the start and reverse the resulting list. This adds O(n²) space for the parent pointers but no change to the time complexity.

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)

Frequently asked questions

BFS guarantees shortest paths specifically when every edge has the same cost — here, every move to a neighbor costs exactly one step. It explores everything at distance 1 before anything at distance 2, so the first time it touches the destination, no shorter route could exist. If moves had different costs (say, diagonal moves cost more than straight ones), you'd need Dijkstra's algorithm instead.

The problem statement explicitly allows diagonal movement — a cell is connected to any neighbor sharing an edge or a corner. Missing the four diagonals is the single most common bug on this problem: it doesn't crash, it just silently returns a longer path (or -1 when a diagonal-only route was the real answer, as in Example 1).

Plain DFS finds a path, not the shortest one — it would need to explore every path and keep the best, which is exactly the exponential brute force above. DFS is the right tool when you need to enumerate or count paths, not when you need the shortest one under uniform step cost.

Finding the fewest hops through a set of nodes where some are unavailable is a direct analogue of routing a request through a mesh or overlay network with some nodes down, or finding the shortest dependency chain through a directed acyclic build graph. BFS-on-a-grid is often the simplest sandbox to practice that reasoning before applying it to a real topology.

A bidirectional BFS — growing a search frontier from both the start and the end simultaneously, stopping when they meet — explores roughly half the area in practice, though it doesn't change the worst-case O(n²) bound. It's a reasonable follow-up to raise if an interviewer asks for something faster, but it isn't necessary to reach the optimal time complexity here.