LeetCode 1091: Shortest Path in Binary Matrix Solution
Master LeetCode problem 1091 (Shortest Path in Binary Matrix), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1091. Shortest Path in Binary Matrix
Problem Explanation
Explanation
To find the length of the shortest clear path in the binary matrix, we can use Breadth First Search (BFS) algorithm. We start from the top-left cell and explore all valid adjacent cells in 8 directions while keeping track of the distance from the starting cell. We continue this process until we reach the bottom-right cell or exhaust all possible paths. If we reach the bottom-right cell, we return the length of the path; otherwise, we return -1.
Algorithm:
- Initialize a queue for BFS, add the starting cell (0, 0) to the queue, and set its distance as 1.
- While the queue is not empty:
- Pop the front cell from the queue.
- Check if it is the bottom-right cell, if yes, return its distance.
- Explore all valid adjacent cells in 8 directions that are within the matrix boundaries and have value 0. Add them to the queue with updated distance (current cell distance + 1).
- If the loop completes without reaching the bottom-right cell, return -1.
Time Complexity: O(n^2) where n is the size of the grid
Space Complexity: O(n^2) for the queue and visited array
Solution Code
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
grid[0][0] = 1;
int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];
if (x == n-1 && y == n-1) return grid[x][y];
for (int[] dir : dirs) {
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && grid[newX][newY] == 0) {
queue.offer(new int[]{newX, newY});
grid[newX][newY] = grid[x][y] + 1;
}
}
}
return -1;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1091 (Shortest Path in Binary Matrix)?
This page provides optimized solutions for LeetCode problem 1091 (Shortest Path in Binary Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1091 (Shortest Path in Binary Matrix)?
The time complexity for LeetCode 1091 (Shortest Path in Binary Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1091 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1091 in Java, C++, or Python.