1091.Shortest_Path_in_Binary_Matrix(Medium).md

1091. Shortest Path in Binary Matrix (Medium)

Date and Time: Dec 5, 2024, 11:00 (EST)

Link: https://leetcode.com/problems/shortest-path-in-binary-matrix

Question:

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

Walk-through:

We can first check if top-left and bottom-right is not 1 (reachable). If not, we can return -1 right away.

Use deque[] to save neighbors, and visited() to mark all the visited cells. Then, we run BFS to find the shortest path. We need to restrict each time we only check the neighbors in deque[] in the same level. So we only update res += 1 after we traverse all the same level neighbors.

If we find a cell is the bottom-right, we return res. Otherwise, if the deque is empty, we return -1 since we can't reach the bottom-right cell.

Python Solution:

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # Run BFS from top-left (0,0) cell to bottom-right (n-1,n-1) cell
        # If top-left or bottom-right is 1, we can return -1 right away
        
        # TC: O(n^2), n = len(grid), SC: O(n^2)
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
        deque = collections.deque()
        deque.append((0, 0))
        visited = set()
        visited.add((0, 0))
        res = 1
        n = len(grid)
        directions = [[-1, 0],[1, 0],[0, 1],[0, -1],[-1, 1],[1, -1],[-1, -1],[1, 1]]
        while deque:
            # Check all the neighbors in the same level
            for _ in range(len(deque)):
                row, col = deque.popleft()
                if row == n - 1 and col == n - 1:
                    return res
                for dr, dc in directions:
                    r, c = dr + row, dc + col
                    # Check valid (r, c) in bound and not in visited and not 1
                    if r in range(n) and c in range(n) and grid[r][c] != 1 and (r, c) not in visited:
                        deque.append((r, c))
                        visited.add((r, c))
            res += 1
        return -1

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$