Code Implementation

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid):
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1

        directions = [(-1, -1), (-1, 0), (-1, 1),
                      (0, -1),          (0, 1),
                      (1, -1),  (1, 0), (1, 1)]
        queue = deque()
        queue.append((0, 0, 1))  # (row, col, path_length)
        visited = set((0, 0))

        while queue:
            r, c, length = queue.popleft()
            if r == n - 1 and c == n - 1:
                return length
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n and
                    grid[nr][nc] == 0 and (nr, nc) not in visited):
                    visited.add((nr, nc))
                    queue.append((nr, nc, length + 1))
        return -1
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        vector<pair<int,int>> dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        queue<tuple<int,int,int>> q;
        q.emplace(0, 0, 1);
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;

        while (!q.empty()) {
            auto [r, c, len] = q.front(); q.pop();
            if (r == n - 1 && c == n - 1) return len;
            for (auto [dr, dc] : dirs) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
                    grid[nr][nc] == 0 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.emplace(nr, nc, len + 1);
                }
            }
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
        int[][] directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], len = curr[2];
            if (r == n - 1 && c == n - 1) return len;
            for (int[] d : directions) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n
                    && grid[nr][nc] == 0 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, len + 1});
                }
            }
        }
        return -1;
    }
}
      

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    const n = grid.length;
    if (grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;
    const directions = [
        [-1,-1], [-1,0], [-1,1],
        [0,-1],          [0,1],
        [1,-1],  [1,0],  [1,1]
    ];
    const queue = [[0, 0, 1]];
    const visited = Array.from({length: n}, () => Array(n).fill(false));
    visited[0][0] = true;

    while (queue.length) {
        const [r, c, len] = queue.shift();
        if (r === n - 1 && c === n - 1) return len;
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (
                nr >= 0 && nr < n && nc >= 0 && nc < n &&
                grid[nr][nc] === 0 && !visited[nr][nc]
            ) {
                visited[nr][nc] = true;
                queue.push([nr, nc, len + 1]);
            }
        }
    }
    return -1;
};
      

Problem Description

You are given an n x n binary matrix called grid. Your goal is to find the length of the shortest clear path from the top-left cell (grid[0][0]) to the bottom-right cell (grid[n-1][n-1]).

• A clear path means every cell along the path has a value of 0 (not blocked).
• You can move to any of the 8 neighboring cells (including diagonals) in one step.
• If there is no such path, return -1.
• You cannot revisit a cell once it’s part of your path.
• There may be multiple possible paths; you must find the shortest one.

The input matrix is always square. The path length is defined as the number of cells visited, including the start and end cells.

Thought Process

Let's break down the requirements and think about how to approach the problem:

• Since we need to find the shortest path in an unweighted grid, our first thought should be a Breadth-First Search (BFS). BFS naturally finds the shortest path in such settings because it explores all paths of length k before moving to paths of length k+1.
• A brute-force approach (trying all possible paths) would be extremely slow, especially for larger grids, because the number of possible paths grows exponentially.
• We must also ensure we do not revisit cells, as this could lead to cycles and incorrect path lengths.
• Since movement is allowed in all 8 directions, we need to account for diagonals as well as orthogonal moves.
• If either the start or end cell is blocked, the answer is immediately -1.

The key insight is that BFS, combined with marking visited cells, will efficiently find the answer without redundant work.

Solution Approach

Let's walk through the steps of the algorithm:

1. Check the start and end: If grid[0][0] or grid[n-1][n-1] is 1 (blocked), return -1 immediately.
2. Set up BFS: Use a queue to store the current cell's coordinates and the path length to reach it.
3. Track visited cells: Use a set or a boolean matrix to remember which cells have already been part of a path, so we don't revisit them.
4. Define directions: List all 8 possible moves (up, down, left, right, and the 4 diagonals).
5. Process the queue:
   • Remove a cell from the queue.
   • If it's the bottom-right cell, return the current path length.
   • For each of its 8 neighbors, if the neighbor is within bounds, not blocked, and not visited, add it to the queue and mark as visited.
6. If the queue is empty and the end is not reached, return -1.

This approach guarantees that the first time we reach the end cell, it is via the shortest possible path.

Example Walkthrough

Let's consider the following input:

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

1. Start at (0,0). It's clear, so we begin BFS with path length = 1.
2. From (0,0), the only valid move is to (1,1) (diagonal down-right), since (0,1) and (1,0) are blocked.
3. Now at (1,1) with path length = 2. From here, valid moves are (2,0) and (2,1).
4. Add (2,0) and (2,1) to the queue with path length = 3.
5. Next, from (2,0), the only valid unvisited neighbor is (2,1), but it's already in the queue.
6. From (2,1), we can move to (2,2) (the end cell).
7. Reaching (2,2) at path length = 4. Return 4.

The shortest path is: (0,0) -> (1,1) -> (2,1) -> (2,2), which is 4 steps.

Time and Space Complexity

• Brute-Force:
  • Would try all possible paths, leading to exponential time complexity: O(2^{n^2}) in the worst case, which is completely infeasible for even small grids.
• Optimized BFS Approach:
  • Time Complexity: O(n^2), because each cell is visited at most once, and we process up to 8 neighbors for each.
  • Space Complexity: O(n^2), for the visited matrix and the queue in the worst case.

BFS is optimal for this problem because it explores all shortest paths first and avoids unnecessary exploration.

Summary

The "Shortest Path in Binary Matrix" problem is a classic application of BFS for grid-based pathfinding. The crucial insights are:

• BFS ensures the shortest path is found in an unweighted grid.
• Marking cells as visited prevents cycles and redundant work.
• Checking edge cases (blocked start/end) saves unnecessary computation.
• The solution is both efficient and elegant, scaling well even for large grids.

Mastering this approach is foundational for many grid and graph traversal problems in programming interviews.