1091. Shortest Path in Binary Matrix (Medium)

Problem

Given an n x n binary grid, a clear path goes from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1) through cells with value 0, moving in any of 8 directions (including diagonals). The length of the path is the number of cells visited. Return the length of the shortest clear path, or -1 if no such path exists.

Example

grid = [[0,1],[1,0]] → 2 (path: (0,0) -> (1,1))
grid = [[0,0,0],[1,1,0],[1,1,0]] → 4 (path: (0,0) -> (0,1) -> (1,2) -> (2,2), length 4)
grid = [[1,0,0],[1,1,0],[1,1,0]] → -1 (start blocked)

LeetCode 1091 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: BFS from top-left, 8 directions

BFS guarantees the first time we reach the destination, it is via the shortest path. Mark cells as visited by setting grid[r][c] = 1 in place to avoid a separate visited set. Return -1 immediately if the start or end is blocked.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)                                              # L1: grid is n x n
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1                                              # L2: O(1) start or end blocked

    if n == 1:
        return 1                                               # L3: O(1) single cell

    q = deque([(0, 0, 1)])                                     # L4: O(1) seed (row, col, dist)
    grid[0][0] = 1                                             # L5: O(1) mark start visited

    DIRS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]  # L6: 8 directions

    while q:                                                   # L7: BFS loop
        r, c, dist = q.popleft()                               # L8: O(1) dequeue
        for dr, dc in DIRS:                                    # L9: O(1) per direction (8 total)
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                if nr == n - 1 and nc == n - 1:
                    return dist + 1                            # L10: O(1) reached destination
                grid[nr][nc] = 1                               # L11: O(1) mark visited
                q.append((nr, nc, dist + 1))                  # L12: O(1) enqueue

    return -1                                                  # L13: O(1) destination unreachable

function shortestPathBinaryMatrix(grid: number[][]): number {
    const n = grid.length;                                     // L1: grid is n x n
    if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;  // L2: start or end blocked

    if (n === 1) return 1;                                     // L3: single cell

    const q: [number, number, number][] = [[0, 0, 1]];        // L4: seed (row, col, dist)
    grid[0][0] = 1;                                            // L5: mark start visited

    const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];  // L6: 8 directions

    let head = 0;
    while (head < q.length) {                                  // L7: BFS loop
        const [r, c, dist] = q[head++];                        // L8: O(1) dequeue
        for (const [dr, dc] of DIRS) {                         // L9: O(1) per direction
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
                if (nr === n - 1 && nc === n - 1) return dist + 1;  // L10: reached destination
                grid[nr][nc] = 1;                              // L11: mark visited
                q.push([nr, nc, dist + 1]);                    // L12: enqueue
            }
        }
    }

    return -1;                                                 // L13: destination unreachable
}

final class Solution {
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        let n = grid.count
        if grid[0][0] != 0 || grid[n - 1][n - 1] != 0 { return -1 }
        var queue = [(0, 0, 1)]
        var head = 0
        var seen = Set([0])
        while head < queue.count {
            let (row, col, distance) = queue[head]
            head += 1
            if row == n - 1 && col == n - 1 { return distance }
            for dr in -1...1 {
                for dc in -1...1 where dr != 0 || dc != 0 {
                    let nr = row + dr, nc = col + dc
                    let key = nr * n + nc
                    if nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 && !seen.contains(key) {
                        seen.insert(key)
                        queue.append((nr, nc, distance + 1))
                    }
                }
            }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = grid side length, so n² = total cells.

Line	Per-call cost	Times executed	Contribution
L2, L3 (guards)	$O(1)$	1	$O(1)$
L4 (seed queue)	$O(1)$	1	$O(1)$
L8 (dequeue)	$O(1)$	at most n²	$O(n²)$
L9 (direction loop)	$O(1)$ × 8	once per dequeued cell	$O(n²)$ ← dominates
L11 (mark visited)	$O(1)$	at most n²	$O(n²)$
L12 (enqueue)	$O(1)$	at most n²	$O(n²)$

Each cell enters the queue at most once (L11 marks it visited before L12 enqueues it). The direction constant 8 is absorbed into the O notation.

Complexity

Time: $O(n²)$ , driven by L8/L9 (each cell dequeued at most once, 8 directions checked).
Space: $O(n²)$ queue worst case (all cells 0 and BFS frontier fills the grid).

Why in-place mutation for visited

Setting grid[nr][nc] = 1 at L11 serves as the visited marker. Without it, the same 0-cell could be enqueued multiple times from different neighbors, causing $O(n² × 8)$ enqueue operations instead of $O(n²)$ . Mark before enqueue, not after dequeue.

8-direction vs 4-direction

4-direction (no diagonals):      8-direction (with diagonals):
      N                              NW  N  NE
      |                               \ | /
  W --+-- E                        W --+-- E
      |                               / | \
      S                              SW  S  SE

This problem uses 8-direction movement. The neighbor formula adds (-1,-1) through (1,1) excluding (0,0).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
DFS	$O(n²)$	$O(n²)$	Does not guarantee shortest path
BFS	$O(n²)$	$O(n²)$	Canonical, guarantees shortest

Always use BFS (not DFS) for shortest path on unweighted graphs.

# Quick smoke tests, paste into a REPL or save as test_1091.py and run.
# Uses the canonical BFS implementation.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    if n == 1:
        return 1
    q = deque([(0, 0, 1)])
    grid[0][0] = 1
    DIRS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    while q:
        r, c, dist = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                if nr == n - 1 and nc == n - 1:
                    return dist + 1
                grid[nr][nc] = 1
                q.append((nr, nc, dist + 1))
    return -1

def _run_tests():
    # Example 1: diagonal shortcut
    assert shortest_path_binary_matrix([[0,1],[1,0]]) == 2

    # Example 2: longer path
    assert shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]]) == 4

    # Start blocked
    assert shortest_path_binary_matrix([[1,0,0],[1,1,0],[1,1,0]]) == -1

    # End blocked
    assert shortest_path_binary_matrix([[0,0,0],[0,0,0],[0,0,1]]) == -1

    # Single clear cell
    assert shortest_path_binary_matrix([[0]]) == 1

    # Single blocked cell
    assert shortest_path_binary_matrix([[1]]) == -1

    # All clear 2x2: path length 2 (diagonal)
    assert shortest_path_binary_matrix([[0,0],[0,0]]) == 2

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function shortestPathBinaryMatrix(grid: number[][]): number {
    const n = grid.length;
    if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
    if (n === 1) return 1;
    const q: [number, number, number][] = [[0, 0, 1]];
    grid[0][0] = 1;
    const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    let head = 0;
    while (head < q.length) {
        const [r, c, dist] = q[head++];
        for (const [dr, dc] of DIRS) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
                if (nr === n - 1 && nc === n - 1) return dist + 1;
                grid[nr][nc] = 1;
                q.push([nr, nc, dist + 1]);
            }
        }
    }
    return -1;
}

console.assert(shortestPathBinaryMatrix([[0,1],[1,0]]) === 2);
console.assert(shortestPathBinaryMatrix([[0,0,0],[1,1,0],[1,1,0]]) === 4);
console.assert(shortestPathBinaryMatrix([[1,0,0],[1,1,0],[1,1,0]]) === -1);
console.assert(shortestPathBinaryMatrix([[0,0,0],[0,0,0],[0,0,1]]) === -1);
console.assert(shortestPathBinaryMatrix([[0]]) === 1);
console.assert(shortestPathBinaryMatrix([[1]]) === -1);
console.assert(shortestPathBinaryMatrix([[0,0],[0,0]]) === 2);
console.log("all tests pass");

01 Matrix, multi-source BFS on a binary grid for distances
Number of Islands, BFS-on-grid component template
Rotting Oranges, multi-source BFS spreading on a grid

BFS, the level order frontier pattern for shortest unweighted distance and wave expansion.
Shortest Paths, the frontier model for minimizing distance, cost, or probability through a graph.

1091. Shortest Path in Binary Matrix (Medium)

Problem

Try it yourself

Approach: BFS from top-left, 8 directions

Why in-place mutation for visited

8-direction vs 4-direction

Summary

Test cases

Related topics

Related concepts