Problem statement

Given an n x n binary matrix grid, return the length of the shortest clear path from the top-left cell to the bottom-right cell, or -1 if none exists.

A clear path visits only cells holding 0, moves between cells that share a side or a corner, and its length is the number of cells it visits.

Example 1

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

Example 2

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

Example 3

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

Constraints

• 1 <= grid.length <= 12
• grid[i].length == grid.length
• grid[i][j] is 0 or 1.

Hints for Shortest Path in Binary Matrix

1. Hint 1

   Every move costs the same, so breadth-first search finds the shortest path.

2. Hint 2

   Eight directions, not four — diagonals count here.

3. Hint 3

   Reject immediately if either corner is blocked, and count cells rather than steps.

How to solve Shortest Path in Binary Matrix

Unweighted shortest path in eight directions: BFS from the top-left, counting cells visited.

Approach

1. Return -1 if either corner is blocked.
2. BFS with dist[0][0] = 1, expanding to the eight neighbours that are 0 and unvisited.
3. Return dist at the bottom-right when dequeued, else -1.

Why it works

BFS visits cells in non-decreasing distance order, so the first time the destination is dequeued its distance is minimal.

Complexity

• Time — O(n²)
• Space — O(n²)

Pitfalls

• Length counts cells, so a 1×1 clear grid answers 1.

Reference solution

Python

from collections import deque

def shortestPathBinaryMatrix(grid) -> int:
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1
    dist = [[-1] * 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):
                if dr == 0 and dc == 0:
                    continue
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
    return -1

Java

public static int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, -1);
    dist[0][0] = 1;
    Deque<int[]> queue = new ArrayDeque<>();
    queue.addLast(new int[]{0, 0});
    while (!queue.isEmpty()) {
        int[] cell = queue.pollFirst();
        if (cell[0] == n - 1 && cell[1] == n - 1) return dist[cell[0]][cell[1]];
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                int nr = cell[0] + dr, nc = cell[1] + dc;
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                if (grid[nr][nc] == 1 || dist[nr][nc] != -1) continue;
                dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
                queue.addLast(new int[]{nr, nc});
            }
        }
    }
    return -1;
}

C++

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
    vector<vector<int>> dist(n, vector<int>(n, -1));
    dist[0][0] = 1;
    vector<pair<int,int>> queue;
    queue.push_back(make_pair(0, 0));
    size_t head = 0;
    while (head < queue.size()) {
        pair<int,int> cell = queue[head++];
        if (cell.first == n - 1 && cell.second == n - 1) return dist[cell.first][cell.second];
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                int nr = cell.first + dr, nc = cell.second + dc;
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                if (grid[nr][nc] == 1 || dist[nr][nc] != -1) continue;
                dist[nr][nc] = dist[cell.first][cell.second] + 1;
                queue.push_back(make_pair(nr, nc));
            }
        }
    }
    return -1;
}

JavaScript

var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;
    const dist = [];
    for (let r = 0; r < n; r++) {
        const row = [];
        for (let c = 0; c < n; c++) row.push(-1);
        dist.push(row);
    }
    dist[0][0] = 1;
    const queue = [[0, 0]];
    let head = 0;
    while (head < queue.length) {
        const cell = queue[head++];
        if (cell[0] === n - 1 && cell[1] === n - 1) return dist[cell[0]][cell[1]];
        for (let dr = -1; dr <= 1; dr++) {
            for (let dc = -1; dc <= 1; dc++) {
                if (dr === 0 && dc === 0) continue;
                const nr = cell[0] + dr, nc = cell[1] + dc;
                if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                if (grid[nr][nc] === 1 || dist[nr][nc] !== -1) continue;
                dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
                queue.push([nr, nc]);
            }
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium