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
.
Flowchart Walkthrough
Here's the algorithm analysis for LeetCode 1091. Shortest Path in Binary Matrix using the algorithm flowchart. Please follow the step-by-step decision path for understanding the choice of algorithm:
Let's begin with the algorithm flowchart which can be found here.
Is it a graph?
- Yes: The binary matrix can be seen as a graph where each cell is a node connected to its adjacent cells (including diagonals if they are not blocked).
Is it a tree?
- No: The binary matrix representation includes multiple possible paths from the start to the end, and it can have cycles formed by multiple access paths to various cells.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem does not specifically pertain to directed acyclic graphs, as connections between nodes (cells) are not directional dependent only progressing from one specific point to another.
Is the problem related to shortest paths?
- Yes: The objective is to find the shortest path from the top-left corner to the bottom-right corner, if it exists.
Is the graph weighted?
- No: Each step from one cell to a neighboring cell that’s not blocked represents an equal cost or distance, conventionally treated as unweighted where each move has a weight of 1.
Conclusion: The flowchart suggests using BFS for this unweighted shortest path problem in a grid. Breadth-First Search (BFS) is ideal for unweighted shortest path issues as it explores all possibilities level by level, ensuring that once it reaches the target, the path used is the shortest possible in terms of the number of edges traversed.
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:
-
Starting Point: First, we check if the starting cell
(0, 0)
is a1
(which would block the path). If it is, we immediately return-1
since we cannot start the path. If it's a0
, we can proceed by marking it as visited (1
in this implementation) to prevent backtracking and initialize our queue with this position. -
The Queue: We use a queue to manage the cells to visit next. It initially contains just the starting cell.
-
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. -
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).
-
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. -
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.
-
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:
-
Validate Start: Before starting the search, we check if the starting cell (top-left corner) is
0
. If it's1
(blocking the path), we return-1
. -
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 to1
to mark it as visited. Theans
variable is initialized to1
, indicating the current path length we're at (starting with the first cell). -
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.
-
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. -
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. -
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. -
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. -
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 EvaluatorExample 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:
-
Validate Start: We check if the starting cell
grid[0][0]
is0
. Since it is, we can proceed. -
Initial Setup: We initialize our queue
q
with((0, 0), 1)
, the starting cell coordinates and the initial path length. The cellgrid[0][0]
is marked as visited by setting it to1
. -
Queue Processing: We begin the loop since our queue is not empty.
-
Current Level Exploration: Our
q
initially contains one element, so we will explore this level with just one loop iteration. -
Neighbor Exploration: We pop
(0, 0)
from the queue. We explore all possible neighbors:- The right cell
(0, 1)
is within bounds and is0
. We mark it visited, and add it to the queue. - The bottom cell
(1, 0)
is within bounds and is0
. We mark it visited, and add it to the queue. - The diagonal cell
(1, 1)
is within bounds but is1
, 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)]
. - The right cell
-
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 be2
. -
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 and0
. 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 and0
. 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)]
. - We first process
-
Reaching Goal: Continuing the loop, we then process
(1, 2)
; its diagonal neighbor is the end cell(2, 2)
, and since it is0
, it means we have reached our destination. We return the current path lengthans
, which is now3
.
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 isN^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 toN^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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.