Pseudo-code

text
function dfs(row, col, count):
    if out_of_bounds OR cell_is_1 OR visited: return
    if row == n-1 AND col == n-1:
        min_path = min(min_path, count)
        return

    mark (row, col) as visited
    for each neighbor in 8 directions:
        dfs(neighbor_row, neighbor_col, count + 1)
    unmark (row, col) // Backtrack

Complexity and Failure Analysis

• Time Complexity: The complexity is exponential, roughly $O(8^{N^2})$ in the worst case. The branching factor is high (up to 8), and because we must find the shortest path, we cannot stop at the first valid path found. We must explore the entire search space.
• Why it fails: This approach will result in a Time Limit Exceeded (TLE) error on LeetCode. DFS is inherently ill-suited for shortest path problems in unweighted graphs because it does not explore paths by length; it explores by depth. It might traverse a path of length 100 before finding a path of length 5.

Core Insight for Shortest Path in Binary Matrix

The critical intuition for LeetCode 1091 is understanding how Breadth-First Search (BFS) explores a graph. Unlike DFS, which dives deep, BFS expands outwards in concentric layers.

1. Layer-by-Layer Expansion: BFS processes all nodes at distance k from the start before processing any node at distance k+1.
2. Shortest Path Guarantee: Because of this layer-by-layer property, the moment BFS reaches the target node (n-1, n-1), we are mathematically guaranteed that the current path length is the minimum possible. We do not need to continue searching.
3. 8-Directional Connectivity: The problem defines connectivity horizontally, vertically, and diagonally. This means each cell has up to 8 edges connecting it to neighbors.

Visual Description: Imagine dropping a stone into a pond at (0, 0). The ripples expand outward uniformly in all directions. The first ripple to touch the bottom-right corner represents the shortest path. Technically, the algorithm maintains a queue. Initially, the queue contains the start node (Layer 0). We dequeue all nodes from Layer 0, identify their valid unvisited neighbors, and enqueue them as Layer 1. This process repeats. The state of the traversal moves from the top-left, filling the available 0 cells like a flood, until the target is reached.

Execution Flow

Let's trace the execution for a simple grid: [[0,1],[1,0]].

1. Start: Check grid[0][0]. It is 0. Valid.
2. Init: Queue = [(0, 0, 1)] (row, col, length). Mark (0, 0) as visited (set to 1).
3. Iteration 1:
   • Dequeue (0, 0, 1).
   • Target is (1, 1). Current is (0, 0). Not target.
   • Explore neighbors of (0, 0).
     • Neighbor (0, 1): Value is 1. Blocked. Ignore.
     • Neighbor (1, 0): Value is 1. Blocked. Ignore.
     • Neighbor (1, 1): Value is 0. Valid.
       • Mark (1, 1) as visited.
       • Enqueue (1, 1, 2).
4. Iteration 2:
   • Dequeue (1, 1, 2).
   • Target is (1, 1). Current is (1, 1). Match found.
   • Return distance 2.

Proof of Correctness

The correctness of this BFS solution relies on the Monotonicity of Path Lengths.

• Invariant: At any point in time, if the queue contains nodes at distance $d$ and $d+1$, all nodes at distance $<d$ have already been processed and removed from the queue.
• Optimality: When we extract the target node $(n-1, n-1)$ from the queue with distance $k$, it implies that we have already processed all reachable nodes with distance $<k$. Therefore, no path with length less than $k$ exists.
• Termination: Since there are a finite number of cells ($N \times N$) and we only visit each cell once, the algorithm is guaranteed to terminate.

Reference Implementation

C++ Solution for LeetCode 1091

cpp
class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        
        // Edge case: Start or end is blocked
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
            return -1;
        }
        
        // Queue stores {row, col}
        queue<pair<int, int>> q;
        q.push({0, 0});
        
        // Mark as visited by overwriting the grid to 1
        grid[0][0] = 1;
        
        // 8-directional offsets
        int directions[8][2] = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},           {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };
        
        int pathLength = 1;
        
        while (!q.empty()) {
            int levelSize = q.size();
            
            // Process current level
            for (int i = 0; i < levelSize; i++) {
                auto [r, c] = q.front();
                q.pop();
                
                // Check if reached bottom-right
                if (r == n - 1 && c == n - 1) {
                    return pathLength;
                }
                
                // Explore neighbors
                for (auto& dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
                    
                    // Check bounds and if cell is 0 (clear/unvisited)
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                        q.push({nr, nc});
                        grid[nr][nc] = 1; // Mark visited immediately
                    }
                }
            }
            pathLength++;
        }
        
        return -1;
    }
};

Java Solution for LeetCode 1091

java
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        
        // Edge case: Start or end is blocked
        if (grid[0][0] == 1 || grid[n-1][n-1] == 1) {
            return -1;
        }
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        grid[0][0] = 1; // Mark visited
        
        int[][] directions = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},           {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };
        
        int pathLength = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int r = current[0];
                int c = current[1];
                
                if (r == n - 1 && c == n - 1) {
                    return pathLength;
                }
                
                for (int[] dir : directions) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];
                    
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                        queue.offer(new int[]{nr, nc});
                        grid[nr][nc] = 1; // Mark visited immediately
                    }
                }
            }
            pathLength++;
        }
        
        return -1;
    }
}

Python Solution for LeetCode 1091

python
from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        # Edge case: Start or end is blocked
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1
            
        queue = deque([(0, 0, 1)]) # row, col, path_length
        grid[0][0] = 1 # Mark visited
        
        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1)
        ]
        
        while queue:
            r, c, dist = queue.popleft()
            
            if r == n - 1 and c == n - 1:
                return dist
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1 # Mark visited immediately
                    queue.append((nr, nc, dist + 1))
                    
        return -1

• Queue: In the worst case (e.g., a diamond shape of expansion), the queue can store proportional to $O(N)$ nodes (specifically the perimeter of the wavefront). However, strictly speaking, the visited set or the grid modification requires $O(N^2)$ space.
• Visited Array: If we use a separate visited array, it takes $O(N^2)$. If we modify the input grid in-place, the auxiliary space is determined by the queue size, which is $O(N^2)$ in the absolute worst case of a dense graph fill, though typically closer to $O(N)$.