LeetCode #1091 Medium

Shortest Path in Binary Matrix

Find the shortest 8-directionally connected path of 0-cells from top-left to bottom-right.

bfsgrid8-directional

02

Intuition

Two traps sink most first attempts. The first is using only 4 directions out of habit; this problem explicitly allows diagonal moves, so a 4-direction BFS can report a path longer than the true shortest, or miss one entirely. The second is marking a cell visited when it is dequeued instead of when it is enqueued; if you wait until dequeue, the same cell can be pushed onto the queue many times before it is ever processed, and the run time degrades badly. Mark on enqueue, expand in all 8 directions, and standard BFS distance-by-layer logic gives the answer.

How to spot this pattern

BFS on an 8-connected grid — diagonals count, so the direction list has eight entries rather than four. Path length counts cells, not steps, which is why the start is seeded at distance 1.

03

Approach

1

Guard the endpoints

If the start or end cell is itself blocked (1), no path exists at all, so return -1 immediately without starting BFS.

2

8-directional BFS, mark on enqueue

Push (0,0) with path length 1 and mark it visited right away. For each popped cell, check all 8 neighbors; any open, unvisited neighbor is marked visited the instant it is pushed, not when it is later popped.

3

Stop at the target

The first time the bottom-right cell is popped, its stored path length is the shortest possible, because BFS explores in nondecreasing distance order.

04

Solution & live demo

▶1class Solution:
▶2    def shortestPathBinaryMatrix(self, grid):
▶3        from collections import deque
▶4        n = len(grid)
▶5        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
▶6            return -1
▶7        visited = [[False]*n for _ in range(n)]
▶8        visited[0][0] = True
▶9        q = deque([(0, 0, 1)])
▶10        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
▶11        while q:
▶12            r, c, d = q.popleft()
▶13            if r == n-1 and c == n-1:
▶14                return d
▶15            for dr, dc in dirs:
▶16                nr, nc = r+dr, c+dc
▶17                if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and not visited[nr][nc]:
▶18                    visited[nr][nc] = True
▶19                    q.append((nr, nc, d+1))
▶20        return -1

05

Common pitfalls

Using only four directions

✗ Wrong

dirs = [(-1,0),(1,0),(0,-1),(0,1)]

✓ Right

dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

The problem allows diagonal movement, which often halves the path length. Four-way BFS returns a longer path or −1 where a diagonal route exists.

Seeding the distance at 0

✗ Wrong

q = deque([(0, 0, 0)])

✓ Right

q = deque([(0, 0, 1)])

The path length is the number of visited cells, and the start cell counts as one. Seeding 0 returns every answer one short — including 0 for a 1×1 grid where the answer is 1.

Not checking that the endpoints are clear

✗ Wrong

q = deque([(0, 0, 1)])

✓ Right

if grid[0][0] != 0 or grid[n-1][n-1] != 0:
    return -1

A blocked start means the search begins on an illegal cell, and a blocked target means it can never succeed — the BFS would exhaust the grid before returning −1. Checking up front is immediate and clearer.

06

Edge cases

Start or end cell blocked

Return -1 before any traversal.

1x1 grid of [[0]]

Start equals end; answer is 1.

No path exists

Queue empties without reaching the target; return -1.

Diagonal shortcut available

8-directional expansion finds it; a 4-direction BFS would overcount.

07

Complexity

Time

O(n^2)

Space

O(n^2)

Enqueue-time marking guarantees each cell enters the queue at most once.