Leetcode 1091. Shortest Path in Binary Matrix

Problem Explanation

The given problem is an application of the shortest path finding in a 2D grid. Each cell in the grid can be marked as either blocked (1) or unblocked (0). The objective is to find the shortest path from the top left cell to the bottom right cell.

In this problem, cells are 8-directionally connected, meaning that a cell not only shares an edge with its four immediate neighbours but can also move diagonally thus shares corners with its four diagonal neighbours.

If no such path exists, we return -1. If the given grid has only one cell, and it is unblocked, then the path length is 1. If the start or end cells are blocked, it's impossible to reach the end, hence return -1.

We solve this problem using the Breadth First Search (BFS) algorithm. BFS is used in this problem because of its property to find the shortest path in terms of the number of edges from the source to the destination. Here, our source cell is (0,0), and the destination cell is (N–1,N–1). The path length from (0,0) to (r,c) will be the level of cell (r,c) when BFS is applied starting from cell (0,0).

Walkthrough Example

Consider an example where the grid is as follows:

1
2
3Input: [[0,0,0],[1,1,0],[1,1,0]]

The shortest path length is 4 because the path [0,0]->[0,1]->[0,2]->[1,2]->[2,2] is the shortest path from [0,0] to [2,2].

On the other hand,

1
2
3Input: [[0,1],[1,0]]

The shortest path length is 2. We can go from [0,0] to [1,1] directly as cells are 8 directionally connected.

Approach Explanation

BFS keeps track of each layer, starting from the source. The BFS would visit all elements in the grid at distance d before visiting elements at distance d+1 from the source. As we need to find the shortest path from (0,0) to (N-1,N-1), BFS guarantees that our path is the shortest.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
7        n = len(grid)
8        
9        # Check start and end are not blocked
10        if grid[0][0] or grid[-1][-1]: return -1 
11        # If grid has only one unblocked cell
12        if n == 1: return 1 
13        
14        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]
15        queue = deque([(0, 0, 1)]) # (x, y, step)
16        grid[0][0] = 1 # Mark as visited
17        
18        while queue:
19            x, y, step = queue.popleft()
20            if x == y == n - 1: # Reached the destination
21                return step
22            for dx, dy in dirs:
23                nx, ny = x + dx, y + dy
24                if 0 <= nx < n and 0 <= ny < n and not grid[nx][ny]:
25                    queue.append((nx, ny, step + 1))
26                    grid[nx][ny] = 1 # Mark as visited
27        return -1

This Python solution uses BFS for finding the shortest path. If the cell is valid (within the grid boundary) and not blocked, add it in the queue, increment the step by one and mark it as visited.## JavaScript Solution

1
2javascript
3var shortestPathBinaryMatrix = function(grid) {
4    // Checking if start and destination are unblocked
5    if(grid[0][0] || grid[grid.length-1][grid.length-1]) return -1;
6    
7    // Defining directions
8    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];
9    
10    // BFS queue
11    let queue = [[0,0,1]];
12    grid[0][0]=1;
13    
14    while(queue.length!== 0){
15        let [x, y, step] = queue.shift();
16       
17        if(x===grid.length-1 && y===grid[0].length-1) return step;
18    
19        for(let [dx, dy] of dirs){
20            let nx = x+dx, ny = y+dy;
21            
22            if(nx>=0 && nx<grid.length && ny>=0 && ny<grid[0].length && grid[nx][ny]==0){
23                queue.push([nx,ny,step+1]);
24                grid[nx][ny]=1;
25            }
26        }
27    }
28    return -1;
29};

In the JavaScript solution also, BFS is utilized to find the shortest path. Here, the directions array consists of the 8 possible grid cell movements. If a grid cell is within the grid boundary and not blocked, it's processed and marked as visited.

Java Solution

1
2java
3public int shortestPathBinaryMatrix(int[][] grid) {
4    int n = grid.length;
5    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
6    Queue<int[]> queue = new LinkedList<>();
7    queue.add(new int[]{0,0,1});
8    int[][] dirs = new int[][]{{0,1}, {0,-1}, {1,0}, {-1,0}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};
9    while (!queue.isEmpty()) {
10        int[] cell = queue.poll();
11        if (cell[0] == n - 1 && cell[1] == n - 1) {
12            return cell[2];
13        }
14        for (int[] dir : dirs) {
15            int newX = cell[0] + dir[0], newY = cell[1] + dir[1];
16            if (newX >= 0 && newY >= 0 && newX < n && newY < n && grid[newX][newY] == 0) {
17                queue.add(new int[]{newX, newY, cell[2] + 1});
18                grid[newX][newY] = 1;
19            }
20        }
21    }       
22    return -1;
23}

In the Java solution, the concept is the same as the previous solutions but the syntax changes. Instead of deque or shift operation, we use a Queue and poll operation respectively. For each valid and unvisited cell, we add it in the queue and marked it as visited.

All the solutions assume the grid is always square.