< Back





1091. Shortest Path in Binary Matrix

Given a matrix of 0s and 1s, we're asked to start from grid[0][0] and make our way to
grid[n-1][n-1] with the shortest path possible. This can be done using breadth-first search. We use
the grid to keep track of the distance we've seen so far, which also helps us mark a location as
seen.

The solution is as follows:


  class Solution:
      def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
          if grid[0][0] != 0 or grid[-1][-1] != 0:
              return -1

          n = len(grid)
          directions = [
              (-1, -1),
              (-1, 0),
              (-1, 1),
              (0, -1),
              (0, 1),
              (1, -1),
              (1, 0),
              (1, 1),
          ]

          def get_neighbours(row: int, col: int) -> tuple:
              for i_diff, j_diff in directions:
                  i, j = row + i_diff, col + j_diff
                  if -1 < i < n and -1 < j < n and grid[i][j] == 0:
                      yield (i, j)

          queue = []
          queue.append((0, 0))
          grid[0][0] = 1

          while queue:
              curr_queue, queue = queue, []

              for row, col in curr_queue:
                  distance = grid[row][col]

                  if (row, col) == (n - 1, n - 1):
                      return distance

                  for i, j in get_neighbours(row, col):
                      grid[i][j] = distance + 1
                      queue.append((i, j))

          return -1


_ Time Complexity:

  O(m) - We iterate through the edges to perform union_set.

_ Space Complexity:

  O(n) - We track the parents and ranks of each node.