![Shortest Path In Binary Matrix Leetcode Problem 1091 [Python Solution]](https://auditorical.com/wp-content/uploads/2023/10/Shortest-Path-In-Binary-Matrix-Leetcode-Problem-1091-Python-Solution-1.webp)
Shortest Path In Binary Matrix Leetcode Problem 1091 [Python Solution]
Let’s discuss and solve the Shortest Path In Binary Matrix problem, a LeetCode problem with ID 1091.
We’ll provide a detailed Python solution to this problem, explain the reasoning behind our approach, and analyze the time and space complexity.
Let’s dive into it step by step.
Problem Overview
The problem statement is as follows: Given an n x n binary matrix grid, you need to find the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1).
A clear path is defined as a path in the matrix where:
- All visited cells are marked as
0. - You can move in 8 directions, including both adjacent cells and diagonal cells.
- The length of a clear path is defined as the number of visited cells in the path.
If there is no clear path from the top-left to the bottom-right cell, return -1. Let’s take a look at a few examples to understand this better:
Example 1:
Input:
grid = [[0, 1], [1, 0]]Output:
2Example 2:
Input:
grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]Output:
4Example 3:
Input:
grid = [[1, 0, 0], [1, 1, 0], [1, 1, 0]]Output:
-1The problem can be visualized as finding the shortest path in a grid, where 1s represent obstacles, and you can move in 8 possible directions.
Understanding the Constraints
Before we proceed with the solution, let’s understand the constraints of the problem:
- The input grid is a square matrix of size
n x n. - The values in the matrix are either
0or1. - The minimum value of
nis1, and the maximum is100. - Each cell in the matrix can be either empty (
0) or blocked (1).
Shortest Path in Binary Matrix LeetCode Problem Solution
To solve this problem, we’ll use a Breadth-First Search (BFS) approach.
BFS is an excellent choice for finding the shortest path in a grid, especially when we have uniform edge weights (in this case, all edges have the same weight).
Python Solution
Here’s the Python solution to the Shortest Path In Binary Matrix problem using BFS:
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid):
N = len(grid)
q = deque([(0, 0, 1)]) # (row, column, length)
visit = set((0, 0))
directions = [
(0, 1), (1, 0), (0, -1), (-1, 0),
(1, 1), (-1, -1), (1, -1), (-1, 1)
]
while q:
row, col, length = q.popleft()
if (
min(row, col) < 0 or
max(row, col) >= N or
grid[row][col]
):
continue
if row == N - 1 and col == N - 1:
return length
for dr, dc in directions:
if (row + dr, col + dc) not in visit:
q.append((row + dr, col + dc, length + 1))
visit.add((row + dr, col + dc))
return -1
In this Python solution, we use a breadth-first search algorithm to explore the grid while keeping track of the length of the path.
We maintain a queue q to store positions to be explored, a set visit to keep track of visited positions, and a list directions to represent the possible eight directions in which we can move.
The BFS starts from the top-left cell (0, 0) with a length of 1.
We check whether each potential move is within bounds, not an obstacle, and not visited.
If these conditions are met, we add the new position to the queue and mark it as visited.
We continue this process until we reach the bottom-right cell (N - 1, N - 1) and return the length of the shortest clear path.
If no clear path is found, we return -1.
Time and Space Complexity
Now, let’s analyze the time and space complexity of our solution:
Time Complexity: The time complexity of our BFS solution is O(N^2), where N is the size of the grid.
This is because in the worst case, we may visit all cells once.
Space Complexity: The space complexity is O(N^2) as well.
We use a queue that can potentially store all N^2 cells, and we maintain a set to keep track of visited cells.
Reasoning Behind Our Approach
Our approach to solving this problem is based on the Breadth-First Search (BFS) algorithm.
BFS is well-suited for finding the shortest path in a grid when the edge weights are uniform, as is the case here.
The algorithm explores the grid level by level, ensuring that when we reach the destination, we’ve found the shortest clear path.
We begin by initializing a queue to store positions to be explored.
We also use a set to keep track of visited positions to avoid revisiting cells and getting stuck in an infinite loop.
We explore the grid using eight possible directions, including diagonals, and we calculate the length of the path as we move along.
By maintaining a queue and marking visited positions, we ensure that we explore each cell efficiently and avoid visiting the same cell multiple times.
If we reach the destination cell, we return the length of the shortest clear path.
If no clear path is found, we return -1.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
- Number Of Connected Components In An Undirected Graph LeetCode
- Accounts Merge LeetCode
- Verifying An Alien Dictionary LeetCode
Related Interview Questions By Category:
- Word Pattern LeetCode
- Serialize And Deserialize Binary Tree LeetCode
- Next Greater Element I LeetCode
Conclusion
In this blog post, we’ve discussed the Shortest Path In Binary Matrix problem, a LeetCode problem with ID 1091. We provided a Python solution based on the Breadth-First Search (BFS) algorithm, explained the reasoning behind our approach, and analyzed the time and space complexity.
If you found this explanation helpful and want to see more code solutions in various languages, check out Auditorical, where you can find a wealth of free resources to help you prepare for coding interviews and improve your problem-solving skills.
We encourage you to comment, ask questions, make suggestions, and share this content with others.
Problem-solving and coding are collaborative activities, and your input is valuable.
Happy coding!
