Shortest Path Binary Matrix LeetCode 1091

LeetCode 1091 Shortest Path in Binary Matrix gives you an n x n grid where each cell contains either 0 (clear) or 1 (blocked). You must find the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). A clear path consists only of cells with value 0, and you may move in all 8 directions: up, down, left, right, and all four diagonals. The length of the path is measured by the number of cells visited, including the start and end cells.

If no clear path exists — because the start or end cell is blocked, or because the grid is fully surrounded by 1-cells — you must return -1. For a 1x1 grid where grid[0][0] is 0, the answer is 1 because the start is also the destination. The inclusion of diagonal movement is the defining feature of this problem, distinguishing it from standard 4-direction grid BFS problems like Number of Islands.

The key observation is that this is an unweighted graph problem: every cell-to-cell transition costs exactly 1, regardless of direction. This means BFS — which processes nodes layer by layer at increasing distances — is the ideal algorithm. Dijkstra with a priority queue would also work but is unnecessary overhead when all edge weights are equal.

BFS explores the graph in concentric waves radiating outward from the source. In the first wave it visits all cells reachable in exactly 1 step. In the second wave it visits all cells reachable in exactly 2 steps. In general, when BFS first reaches any cell, it has done so via the shortest possible path. This level-by-level expansion is the fundamental reason BFS yields optimal results for unweighted shortest paths.

The formal argument is by contradiction: if BFS first reached the destination at distance d but there existed a shorter path of length d' < d, then BFS would have visited the destination during wave d' instead of wave d, which contradicts the assumption that BFS first reached it at wave d. This argument holds as long as all transitions have equal cost — the defining property of an unweighted graph.

DFS does not have this property. DFS follows a single branch as deep as it can go, potentially finding a very long path to the destination before it backtracks to explore shorter alternatives. DFS can tell you whether a path exists, but not that the first path found is the shortest. For shortest-path queries on unweighted graphs, BFS is the canonical and correct choice.

The BFS implementation initializes a queue with the starting cell (0, 0) at distance 1 — because the path length counts cells, and the starting cell itself counts as 1. Before doing anything else, check the edge cases: if grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1 immediately since no clear path can exist. For a 1x1 grid where grid[0][0] == 0, return 1 immediately.

For each cell (r, c, dist) popped from the queue, check all 8 neighbors. For each neighbor (nr, nc) that is in bounds, equals 0, and has not been visited, add it to the queue with distance dist + 1. If the neighbor is the destination (n-1, n-1), return dist + 1 immediately — this is the shortest path by the BFS guarantee.

Mark cells as visited immediately when adding them to the queue, not when popping them. This is a crucial detail: if you wait until a cell is popped to mark it visited, other queue entries can enqueue the same cell multiple times before it is processed. Marking on enqueue ensures each cell appears in the queue at most once, keeping time complexity at O(n^2).

Most grid BFS problems restrict movement to 4 directions: up, down, left, right. LeetCode 1091 expands this to all 8 directions by adding the four diagonals: up-left (-1,-1), up-right (-1,+1), down-left (+1,-1), and down-right (+1,+1). The implementation change is minimal — just replace the 4-element direction array with an 8-element one — but the problem structure changes significantly.

With 8-directional movement, the shortest path can be much shorter than with 4-directional movement. For example, crossing from corner to corner of an n x n all-zero grid takes 2n-1 steps with 4-direction movement but only n steps with 8-direction movement (moving diagonally all the way). This means 8-direction BFS can skip over cells that 4-direction BFS must visit, leading to shorter paths and potentially faster termination.

The standard direction array for 8-direction BFS is: [(-1,-1), (-1,0), (-1,+1), (0,-1), (0,+1), (+1,-1), (+1,0), (+1,+1)]. This covers all combinations of row delta in {-1, 0, +1} and column delta in {-1, 0, +1} except (0, 0). The BFS loop structure is otherwise identical to 4-direction BFS — only this array changes.

The most common source of wrong answers on LeetCode 1091 is missing the early termination checks for blocked start or end cells. If grid[0][0] == 1, no path can start and you must return -1 immediately. If grid[n-1][n-1] == 1, no path can end at the destination and you must return -1 immediately. Failing to check these before starting BFS will produce incorrect results because BFS will terminate with an empty queue and return -1 correctly by accident, but only if the destination cell is never reached — missing the edge case where start is blocked but destination is clear.

The 1x1 grid case is also tricky: if n == 1, the start and destination are the same cell. If grid[0][0] == 0, the path length is 1 (a single cell). If grid[0][0] == 1, return -1. Some implementations handle this naturally through the main BFS loop, but it is safer to check explicitly before starting.

For visited marking, modifying the grid in-place by setting grid[r][c] = 1 after visiting is memory-efficient and avoids allocating a separate boolean matrix. This is acceptable because the problem does not require the grid to be unchanged after the call. If you need to preserve the original grid, use a separate visited boolean array of size n x n initialized to false.

In Python, use collections.deque for O(1) popleft operations. Initialize with deque([(0, 0, 1)]) and immediately check the two edge cases. The direction list is dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]. The main loop calls queue.popleft() and iterates over dirs. Time complexity is O(n^2) because each cell is visited at most once. Space complexity is O(n^2) for the queue in the worst case, plus O(1) extra if marking in-place.

In Java, use ArrayDeque<int[]> where each entry is new int[]{row, col, dist}. Use int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}. Call queue.poll() in the main loop. Java's ArrayDeque is faster than LinkedList for BFS queues. The solution is about 25 lines and handles all constraints cleanly within the n <= 100 limit.

A subtle but important point: the path length counts cells, not edges. The starting cell at (0,0) already contributes 1 to the path length. This is why the queue is initialized with distance 1, not 0. When the destination is reached from a cell at distance dist, the answer is dist + 1 — adding 1 for the destination cell itself. Getting this count wrong is the most common off-by-one error on this problem.

Number of Islands (LeetCode 200) and Number of Islands II (LeetCode 305) are foundational BFS/DFS grid problems where you flood-fill connected components of 1-cells. Rotting Oranges (LeetCode 994) uses multi-source BFS starting from all rotten oranges simultaneously — a pattern where BFS begins from multiple sources at once. Walls and Gates (LeetCode 286) is another multi-source BFS problem where you propagate distances outward from all gates in parallel.

Swim in Rising Water (LeetCode 778) adds a twist by making the graph weighted: you want the minimax path (minimize the maximum cell value), which requires a Dijkstra-style min-heap rather than plain BFS. Path With Minimum Effort (LeetCode 1631) similarly uses Dijkstra on a grid but minimizes the maximum absolute difference between adjacent cells. Shortest Path in Binary Matrix sits between these two worlds — it is unweighted (all moves cost 1) but uses 8-direction movement.

The BFS grid family rewards pattern recognition. Once you know that BFS gives optimal distances in unweighted graphs, problems in this family reduce to recognizing which cells are valid, what the movement rules are, and whether the graph is weighted or unweighted. Shortest Path in Binary Matrix is an excellent practice problem because it is clean, has just enough edge cases to be interesting, and directly trains the mark-on-enqueue habit that is critical for all BFS implementations.