Shortest Path in Binary Matrix

mediumAdvanced Graphs (Dijkstra / MST)204 stepsJava · Python · C++

Find the shortest path of 0-cells from the top-left to the bottom-right, moving in 8 directions. Every move costs the same, so BFS finds the shortest path. Path length counts cells, so the start is 1.

▶ Watch the animated trace

Traced input: grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]] → 4. Original problem: neetcode.io/problems/shortest-path-in-binary-matrix

Complexity

BestO(1)

AverageO(n²)

WorstO(n²)

SpaceO(n²)

Each cell is queued at most once.

Key idea

Unweighted shortest path = BFS.
Diagonal moves count, so check all 8 neighbours.
Mark cells visited when queuing, not when popping, to avoid duplicates.
If the start or end is 1, there's no path.

Common mistakes

Using only 4 directions.
Returning the number of moves instead of the number of cells.

Solution

Java

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];
    dist[0][0] = 1;
    Queue<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{0, 0});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        if (r == n - 1 && c == n - 1) {
            return dist[r][c];
        }
        for (int dr = -1; dr <= 1; dr++)
            for (int dc = -1; dc <= 1; dc++) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] == 1 || dist[nr][nc] != 0) continue;
                dist[nr][nc] = dist[r][c] + 1;
                queue.offer(new int[]{nr, nc});
            }
    }
    return -1;
}

Python

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

C++

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
        return -1;
    }
    vector<vector<int>> dist(n, vector<int>(n));
    dist[0][0] = 1;
    queue<pair<int, int>> q;
    q.push({0, 0});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (r == n - 1 && c == n - 1) {
            return dist[r][c];
        }
        for (int dr = -1; dr <= 1; dr++)
            for (int dc = -1; dc <= 1; dc++) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] == 1 || dist[nr][nc] != 0) continue;
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
    }
    return -1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Blocked start You can't stand on a 1.	`grid = [[1, 0], [0, 0]]`	`-1`
Single cell The path is just the start.	`grid = [[0]]`	`1`
Diagonal shortcut One diagonal move.	`grid = [[0, 1], [1, 0]]`	`2`