1091. Shortest Path in Binary Matrix


Problem Description

The problem presents us with an n x n binary matrix grid, where the objective is to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (n - 1, n - 1). The path is considered clear if it consists only of 0's and all adjacent cells in the path (including diagonally adjacent cells) are connected, meaning every step in the path can move horizontally, vertically, or diagonally to the next cell as long as it remains within the bounds of the grid and is a 0. The length of the path is defined by the number of cells that the path visits. If no such path exists, the function should return -1.

Intuition

To solve this problem, we can employ a Breadth-First Search (BFS) approach. BFS is ideal for finding the shortest path in an unweighted grid because it explores all neighboring cells at the current depth level before moving on to cells at the next level of depth. Here’s how we get there:

  1. Starting Point: First, we check if the starting cell (0, 0) is a 1 (which would block the path). If it is, we immediately return -1 since we cannot start the path. If it's a 0, we can proceed by marking it as visited (1 in this implementation) to prevent backtracking and initialize our queue with this position.

  2. The Queue: We use a queue to manage the cells to visit next. It initially contains just the starting cell.

  3. Visiting Cells: In each step of the BFS, we pop a cell from the queue, process it, and add all its unvisited 0-neighbors to the queue.

  4. Movement: We move to adjacent cells in all 8 possible directions. Since the problem specifies 8-directional connectivity, we have to check all cells around the current cell (horizontally, vertically, and diagonally).

  5. Goal Check: Each time we pop a cell from the queue, we check if it's the bottom-right cell (n - 1, n - 1). If so, we have reached the destination, and we can return the current path length.

  6. Incrementing Path Length: Every time we've checked all neighbors for the current level (cells with the same path length), we increment the path length before moving on to the next level.

  7. Base Case for No Path: If we exhaust the queue without reaching the destination, we return -1, indicating there is no possible path.

The BFS guarantees that the first time we reach the bottom-right cell, that path is the shortest because we have explored in a way that checks all possible paths of incrementally longer lengths. The grid modification (grid[x][y] = 1) acts as a visited marker to avoid revisiting cells and potentially creating loops.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution approach employs Breadth-First Search (BFS) to systematically search for the shortest path from the start to the end of the binary matrix. The BFS algorithm is ideal for such a problem since it exhaustively explores all neighbors of a given cell before moving further away, thereby ensuring the shortest path is found if it exists. Given below is a step-by-step walkthrough of the algorithm:

  1. Validate Start: Before starting the search, we check if the starting cell (top-left corner) is 0. If it's 1 (blocking the path), we return -1.

  2. Initial Setup: We initialise our queue, q, with a tuple representing the starting cell coordinates (0, 0) and set the value of the starting cell to 1 to mark it as visited. The ans variable is initialized to 1, indicating the current path length we're at (starting with the first cell).

  3. Queue Processing: We create a loop that runs as long as the queue is not empty. This queue will store the cells to explore at each level of depth.

  4. Current Level Exploration: Inside the loop, we have an inner loop for _ in range(len(q)):. This ensures that we only process cells that are at the current level of depth, thus maintaining the BFS property.

  5. Neighbor Exploration: We pop the front cell from the queue and check all possible 8 directions around this cell. For each of those directions, we check whether the cell is within the grid bounds and whether it is unvisited (0). If these conditions are met, we mark the cell as visited (grid[x][y] = 1) to prevent revisiting it and add its coordinates to the queue for further exploration.

  6. Goal Condition: If we encounter the bottom-right cell during exploration, we immediately return the current path length (ans), as this is the shortest path due to the BFS.

  7. Incrementing Path Length: Once we have explored all neighbors of the current depth level, we increment ans by 1 to account for the next level that we'll start exploring in the next iteration of the outer loop.

  8. Returning -1: If the loop terminates without finding the bottom-right cell, we return -1, signifying it doesn't have an accessible path.

The choice of a queue in BFS is a fundamental part of the algorithm. It ensures that nodes are explored in the order of their proximity to the start node (level by level, not depth by depth like DFS), which is why the path length is incremented once per level, not per node.

By modifying the grid in-place, we can keep track of visited nodes without the need for an additional visited matrix, which also helps in reducing space complexity.

Overall, the algorithm has a time complexity of O(n^2) if all cells are visited in the worst case and a space complexity of O(n^2) as well, taken up by the queue in the worst case where all cells are added to it.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small 3x3 binary matrix grid as an example to illustrate the solution approach:

1grid = [
2    [0, 0, 0],
3    [0, 1, 0],
4    [1, 0, 0]
5]

We want to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (2, 2) using the BFS approach. Here's a step-by-step walkthrough of what the algorithm would do:

  1. Validate Start: We check if the starting cell grid[0][0] is 0. Since it is, we can proceed.

  2. Initial Setup: We initialize our queue q with ((0, 0), 1), the starting cell coordinates and the initial path length. The cell grid[0][0] is marked as visited by setting it to 1.

  3. Queue Processing: We begin the loop since our queue is not empty.

  4. Current Level Exploration: Our q initially contains one element, so we will explore this level with just one loop iteration.

  5. Neighbor Exploration: We pop (0, 0) from the queue. We explore all possible neighbors:

    • The right cell (0, 1) is within bounds and is 0. We mark it visited, and add it to the queue.
    • The bottom cell (1, 0) is within bounds and is 0. We mark it visited, and add it to the queue.
    • The diagonal cell (1, 1) is within bounds but is 1, so we don't add it to the queue.

    Our queue now looks like this (with corresponding path lengths): [((0, 1), 2), ((1, 0), 2)].

  6. Incrementing Path Length: At this point we complete the first level, so if we didn't find the end cell, we would proceed to the next level and increment ans. Since we found multiple neighbors, ans would be 2.

  7. Processing Next Level: We continue with our BFS loop for the next level.

    • We first process (0, 1). Its right neighbor is outside the grid, bottom neighbor (1, 1) is blocked, and the diagonal bottom-right neighbor (1, 2) is in bounds and 0. We add (1, 2) to the queue and mark it as visited.
    • Next, we process (1, 0). Its neighbors to the right (1, 1) and bottom (2, 0) are blocked, but the diagonal (2, 1) is in bounds and 0. We mark it and add it to the queue.

    Our queue and corresponding path lengths now look like this: [ (1, 2), 3), ((2, 1), 3)].

  8. Reaching Goal: Continuing the loop, we then process (1, 2); its diagonal neighbor is the end cell (2, 2), and since it is 0, it means we have reached our destination. We return the current path length ans, which is now 3.

Since we've reached the goal on this level, we don't need to process any further levels. The shortest path length from the top-left corner to the bottom-right corner is 3.

If at any point we had exhausted the queue without reaching the bottom-right corner, we would return -1. In this example, that is not the case, as we have successfully found a path.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
5        # Check if the starting cell is blocked
6        if grid[0][0] != 0:
7            return -1
8      
9        # Initialize the size of the grid
10        n = len(grid)
11        # Set starting point as visited by marking it with a 1 (path length from the origin)
12        grid[0][0] = 1
13        # Initialize a queue with the starting coordinate
14        queue = deque([(0, 0)])
15        # Initialize path length
16        path_length = 1
17      
18        # Process nodes until the queue is empty
19        while queue:
20            # Loop through all nodes at the current level of breadth
21            for _ in range(len(queue)):
22                i, j = queue.popleft()  # Get next node coordinates
23              
24                # Check if we've reached the target cell
25                if i == j == n - 1:
26                    return path_length
27              
28                # Check all 8 adjacent cells
29                for x in range(i - 1, i + 2):
30                    for y in range(j - 1, j + 2):
31                        # Boundary check and cell is not blocked
32                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
33                            # Mark cell as visited and add its coordinates to the queue
34                            grid[x][y] = 1
35                            queue.append((x, y))
36            # Increment path length at the conclusion of the level
37            path_length += 1
38      
39        # If we exit the loop without returning, no path has been found
40        return -1
41
1class Solution {
2    // Method to find the shortest path in a binary matrix from top-left to bottom-right
3    public int shortestPathBinaryMatrix(int[][] grid) {
4        // If the starting cell is blocked, return -1
5        if (grid[0][0] == 1) {
6            return -1;
7        }
8      
9        // Get the size of the grid
10        int n = grid.length;
11      
12        // Mark the starting cell as visited by setting it to 1
13        grid[0][0] = 1;
14      
15        // Initialize a queue to hold the cells to be visited
16        Deque<int[]> queue = new ArrayDeque<>();
17      
18        // Start from the top-left corner (0, 0)
19        queue.offer(new int[] {0, 0});
20      
21        // Variable to keep track of the number of steps taken
22        for (int steps = 1; !queue.isEmpty(); ++steps) {
23            // Process cells level by level
24            for (int k = queue.size(); k > 0; --k) {
25                // Poll the current cell from the queue
26                int[] cell = queue.poll();
27                int i = cell[0], j = cell[1];
28              
29                // If we have reached the bottom-right corner, return the number of steps
30                if (i == n - 1 && j == n - 1) {
31                    return steps;
32                }
33              
34                // Explore all 8 directions from the current cell
35                for (int x = i - 1; x <= i + 1; ++x) {
36                    for (int y = j - 1; y <= j + 1; ++y) {
37                        // Check for valid cell coordinates and if the cell is not blocked
38                        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
39                            // Mark the cell as visited
40                            grid[x][y] = 1;
41                          
42                            // Add the cell to the queue to explore its neighbors later
43                            queue.offer(new int[] {x, y});
44                        }
45                    }
46                }
47            }
48        }
49      
50        // If the goal was not reached, return -1
51        return -1;
52    }
53}
54
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
8        // If the starting cell is blocked, there is no path.
9        if (grid[0][0] != 0) {
10            return -1;
11        }
12      
13        int n = grid.size(); // Dimension of the grid
14        grid[0][0] = 1; // Mark the starting cell as visited by setting it to 1
15        queue<pair<int, int>> q; // Define a queue to store the cells to visit
16        q.emplace(0, 0); // Start with the top-left corner of the grid
17      
18        // Loop until there are no more cells to visit
19        for (int pathLength = 1; !q.empty(); ++pathLength) {
20            for (int k = q.size(); k > 0; --k) {
21                auto [row, col] = q.front(); // Get the current cell's position
22                q.pop(); // Remove the current cell from the queue
23              
24                // If the current cell is the bottom-right corner, the path is found
25                if (row == n - 1 && col == n - 1) {
26                    return pathLength;
27                }
28              
29                // Iterate through all the neighbors of the current cell
30                for (int x = row - 1; x <= row + 1; ++x) {
31                    for (int y = col - 1; y <= col + 1; ++y) {
32                        // Check if the neighbor is within the grid and is not blocked
33                        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {
34                            grid[x][y] = 1; // Mark the neighbor as visited
35                            q.emplace(x, y); // Add the neighbor to the queue
36                        }
37                    }
38                }
39            }
40        }
41      
42        // If there is no path, return -1
43        return -1;
44    }
45};
46
1function shortestPathBinaryMatrix(grid: number[][]): number {
2    // Early exit if the starting cell (0, 0) is blocked.
3    if (grid[0][0] === 1) {
4        return -1;
5    }
6
7    const gridSize = grid.length;
8    // Occupying the starting point.
9    grid[0][0] = 1;
10
11    // Queue for the BFS, starting with position (0, 0).
12    let queue: number[][] = [[0, 0]];
13  
14    // BFS loop. 'steps' counts the number of steps taken.
15    for (let steps = 1; queue.length > 0; ++steps) {
16        // 'nextQueue' will store the positions to visit in the next loop iteration.
17        const nextQueue: number[][] = [];
18      
19        // Process each cell in the current queue.
20        for (const [row, col] of queue) {
21            // Check if the bottom-right corner is reached.
22            if (row === gridSize - 1 && col === gridSize - 1) {
23                return steps;
24            }
25            // Explore all 8 directions around the current cell.
26            for (let x = row - 1; x <= row + 1; ++x) {
27                for (let y = col - 1; y <= col + 1; ++y) {
28                    // Check if the new position is valid and not blocked.
29                    if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && grid[x][y] === 0) {
30                        // Mark the cell as visited by setting it to 1.
31                        grid[x][y] = 1;
32                        // Add the position to the 'nextQueue'.
33                        nextQueue.push([x, y]);
34                    }
35                }
36            }
37        }
38
39        // Update the queue for the next iteration of BFS.
40        queue = nextQueue;
41    }
42
43    // If the bottom-right corner was never reached, return -1.
44    return -1;
45}
46

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is O(N^2). Here's why:

  • The algorithm employs Breadth-First Search (BFS) which can visit each cell at most once. Since it accounts for 8 possible directions a cell can have, the loop check all adjacent 8 cells.
  • In the worst case, we have to visit all cells in an N x N grid. Each cell is visited once, hence the complexity is proportional to the total number of cells, which is N^2.

Space Complexity

The space complexity of the algorithm is O(N^2) as well.

  • The queue q can potentially store all of the cells in case of a sparse grid (consisting mostly of 0s). Hence, in the worst case, queue space can go up to N^2.
  • The grid itself is modified in place, hence no extra space is used other than the input size, which does not count towards space complexity in this context.
  • No additional significant space is used, as other variables have constant size.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄