Problem of The Day: Shortest Path in Binary Matrix

Problem Statement

Intuition

The problem asks to find the shortest path from the top-left corner to the bottom-right corner in a binary matrix. Each cell in the matrix is either passable (0) or blocked (1). The intuition is to perform a breadth-first search (BFS) since it explores all possible paths level by level, ensuring the first time we reach the destination, it is the shortest path.

Approach

1. We start by checking if the first or last cell is blocked. If either is blocked, there is no path, so we return -1.
2. Then we initialize a queue to perform BFS. The queue will store the coordinates of cells we visit, starting from the top-left corner.
3. For each cell, we check all 8 possible directions (up, down, left, right, and diagonals). If a neighboring cell is within bounds and passable, we mark it as visited by updating its value to the current distance from the start and add it to the queue.
4. The algorithm terminates when we reach the bottom-right corner, returning the distance traveled. If we exhaust all options and never reach the destination, we return -1.

Complexity

• Time complexity: The time complexity is \(O(n^2)\), where n is the number of rows (or columns, assuming the matrix is square). We visit each cell at most once, and checking neighbors is constant work.

• Space complexity: The space complexity is also \(O(n^2)\) due to the queue, which could potentially hold all cells in the matrix in the worst case.

Code

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0 or grid[-1][-1] != 0:
            return -1
        ROWS = len(grid)
        COLS = len(grid[0])
        queue = deque()
        queue.append([0, 0])
        grid[0][0] = 1
        while queue:
            r, c = queue.popleft()
            dist = grid[r][c]
            if r == ROWS - 1 and c == COLS -1:
                return dist
            for x, y in [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]:
                row, col = r + x, c + y
                if 0 <= row < ROWS and 0 <= col < COLS and grid[row][col] == 0:
                    grid[row][col] = dist + 1
                    queue.append([row, col])

        return -1