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.

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

python

▶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

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.

06

Complexity

Time

O(n^2)

Space

O(n^2)

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