Problem 21.2 · Breadth-First SearchMedium

Shortest Path in Binary Matrix

What it teaches: Single-source BFS on a grid with 8-directional moves.

Practise it on judges as “Shortest Path in Binary Matrix”.

The problem

In an n × n grid of 0s (open) and 1s (blocked), return the number of cells on the shortest path from the top-left to the bottom-right, moving in any of 8 directions through 0 cells. Return −1 if there is no path.

Example 1

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

Constraints

1 ≤ n ≤ 100

Pattern clues in the wording

→ Fewest steps on an unweighted grid

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [[0,1],[1,0]]	2
2	grid = [[0,0,0],[1,1,0],[1,1,0]]	4
3	grid = [[1,0,0],[1,1,0],[1,1,0]]	-1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. BFS · O(n²)

BFS

Time O(n²) Space O(n²)

dist[0][0] = 1. BFS over 8 neighbours that are 0 and unvisited. Return dist at the bottom-right.

Approach 1

import java.util.*;

class Solution {
    public 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;
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] cell = q.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;
                    q.offer(new int[]{nr, nc});
                }
        }
        return -1;
    }
}

Verdict: Standard grid BFS.

Before you submit

Edge cases and common mistakes

Test these inputs

1 × 1 grid with 0 (answer 1)
Blocked start or end

Mistakes people make

Counting moves instead of cells (off by one).
Forgetting diagonals.

Interview

Follow-up questions

How could A* speed this up?

Command Palette

The problem

Approaches

BFS

Edge cases and common mistakes

Follow-up questions