#1091 Shortest Path in Binary Matrix

frequently reported atMeta Amazon Google Microsoft

the problem

In plain words

In an n×n grid of 0s (open) and 1s (blocked), find the length of the shortest clear path from the top-left to the bottom-right, moving in 8 directions. Length counts cells. Return -1 if none exists.

in grid = [[0,1],[1,0]]

out 2

One diagonal step: 2 cells.

in grid = [[0,0,0],[1,1,0],[1,1,0]]

out 4

in grid = [[1,0,0],[1,1,0],[1,1,0]]

out -1

The start is blocked.

1 ≤ n ≤ 100
grid[i][j] is 0 or 1

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBFS shortest path (unweighted)

Every move costs 1, so BFS finds the shortest path: the first time BFS pops the target, that's the answer.

solutions

From brute force to optimal

Try every simple path; keep the shortest; prune paths already as long as the best.

Mark the cell on the path, recurse in 8 directions, unmark on return.
At the target, update best.

timeExponential

The number of simple paths in a grid grows exponentially with n²; pruning doesn't change the worst case.

spaceO(n²)

onPath grid and recursion depth up to n².

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};3 4    private int best;5 6    /** Try every simple path with DFS + backtracking and keep the shortest. Exponential. */7    public int shortestPathBinaryMatrix(int[][] grid) {8        int n = grid.length;9        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;10        best = Integer.MAX_VALUE;11        boolean[][] onPath = new boolean[n][n];12        onPath[0][0] = true;13        explore(grid, 0, 0, 1, onPath);14        return best == Integer.MAX_VALUE ? -1 : best;15    }16 17    private void explore(int[][] g, int r, int c, int len, boolean[][] onPath) {18        int n = g.length;19        if (len >= best) return; // can't beat what we already have20        if (r == n - 1 && c == n - 1) {21            best = len;22            return;23        }24        for (int[] d : DIRS) {25            int nr = r + d[0], nc = c + d[1];26            if (nr < 0 || nc < 0 || nr >= n || nc >= n || g[nr][nc] != 0 || onPath[nr][nc]) continue;27            onPath[nr][nc] = true;28            explore(g, nr, nc, len + 1, onPath);29            onPath[nr][nc] = false; // undo: other paths may use this cell30        }31    }32}

BFS with 8 directions, storing the path length in each cell when first discovered.

If start or end is blocked → -1.
len[0][0] = 1; BFS.
When the target is polled, return its length.

timeO(n²)

Each of the n² cells is enqueued at most once; 8 neighbours each.

spaceO(n²)

The length grid and the queue.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};3 4    public int shortestPathBinaryMatrix(int[][] grid) {5        int n = grid.length;6        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;7        int[][] len = new int[n][n]; // cells on the path so far; 0 = unseen8        Deque<int[]> queue = new ArrayDeque<>();9        queue.offer(new int[] {0, 0});10        len[0][0] = 1; // the path length counts cells, so the start alone is 111        while (!queue.isEmpty()) {12            int[] cell = queue.poll();13            int r = cell[0], c = cell[1];14            if (r == n - 1 && c == n - 1) return len[r][c]; // first arrival = shortest15            for (int[] d : DIRS) {16                int nr = r + d[0], nc = c + d[1];17                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] != 0 || len[nr][nc] != 0) continue;18                len[nr][nc] = len[r][c] + 1;19                queue.offer(new int[] {nr, nc});20            }21        }22        return -1;23    }24}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};3 4    public int shortestPathBinaryMatrix(int[][] grid) {5        int n = grid.length;6        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;7        int[][] len = new int[n][n]; // cells on the path so far; 0 = unseen8        Deque<int[]> queue = new ArrayDeque<>();9        queue.offer(new int[] {0, 0});10        len[0][0] = 1; // the path length counts cells, so the start alone is 111        while (!queue.isEmpty()) {12            int[] cell = queue.poll();13            int r = cell[0], c = cell[1];14            if (r == n - 1 && c == n - 1) return len[r][c]; // first arrival = shortest15            for (int[] d : DIRS) {16                int nr = r + d[0], nc = c + d[1];17                if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] != 0 || len[nr][nc] != 0) continue;18                len[nr][nc] = len[r][c] + 1;19                queue.offer(new int[] {nr, nc});20            }21        }22        return -1;23    }24}

in the room

How to say it in the interview

talk track

Check both corners for 1 before anything else.
Clarify that length counts cells, so the start alone is 1.

traps

Using 4 directions — diagonals are allowed here.
Returning steps (cells − 1).

what they ask next

Follow-ups

Faster in practice?

A* with the Chebyshev distance max(|dr|, |dc|) as the heuristic explores fewer cells; worst case is the same.

before you submit

Edge cases to test

n = 1 with grid [[0]] → 1 (the path is the start cell itself).
Start or end blocked → -1 before any search.
Diagonal squeezes count: [[0,1],[1,0]] → 2.

practise next