1091. Shortest Path in Binary Matrix LeetCode Solution

In this guide, you will get 1091. Shortest Path in Binary Matrix LeetCode Solution with the best time and space complexity. The solution to Shortest Path in Binary Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Shortest Path in Binary Matrix solution in C++
Shortest Path in Binary Matrix solution in Java
Shortest Path in Binary Matrix solution in Python
Additional Resources

1091. Shortest Path in Binary Matrix LeetCode Solution image

Problem Statement of Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n – 1, n – 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1091. Shortest Path in Binary Matrix LeetCode Solution in C++

class Solution {
 public:
  int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    const int n = grid.size();
    if (grid[0][0] == 0 && n == 1)
      return 1;
    if (grid[0][0] == 1 || grid.back().back() == 1)
      return -1;

    constexpr int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
                                {0, 1},   {1, -1}, {1, 0},  {1, 1}};
    queue<pair<int, int>> q{{{0, 0}}};
    vector<vector<bool>> seen(n, vector<bool>(n));
    seen[0][0] = true;

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == n || y < 0 || y == n)
            continue;
          if (grid[x][y] != 0 || seen[x][y])
            continue;
          if (x == n - 1 && y == n - 1)
            return step + 1;
          q.emplace(x, y);
          seen[x][y] = true;
        }
      }

    return -1;
  }
};
/* code provided by PROGIEZ */

1091. Shortest Path in Binary Matrix LeetCode Solution in Java

class Solution {
  public int shortestPathBinaryMatrix(int[][] grid) {
    final int n = grid.length;
    if (grid[0][0] == 0 && n == 1)
      return 1;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
      return -1;

    final int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(0, 0)));
    boolean[][] seen = new boolean[n][n];
    seen[0][0] = true;

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().getKey();
        final int j = q.poll().getValue();
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == n || y < 0 || y == n)
            continue;
          if (grid[x][y] != 0 || seen[x][y])
            continue;
          if (x == n - 1 && y == n - 1)
            return step + 1;
          q.offer(new Pair<>(x, y));
          seen[x][y] = true;
        }
      }

    return -1;
  }
}
// code provided by PROGIEZ