Shortest Path In Binary Matrix - Leetcode Solution

The Shortest Path In Binary Matrix problem on LeetCode is to find the shortest path from the top-left corner of a binary matrix to the bottom-right corner, given that only the cells with value 1 can be traversed.

Example input:

[[0,1,0], [1,1,0], [1,1,1]]

Solution:

We can use the Breadth-First Search (BFS) algorithm to solve this problem. The BFS algorithm explores all the nodes in the same level before moving to the next level. We start by visiting the top-left corner of the matrix and then explore all the valid neighbors of this cell. We continue this process until we reach the bottom-right corner of the matrix. The distance of the destination node will be the shortest path.

Algorithm:

1. Initialize a queue with the first cell. Add a tuple to the queue with the first cell coordinates and distance set to 1.
2. Create a visited matrix to avoid revisiting the same cell.
3. Define valid moves from the current cell, i.e., valid moves are only to the cells with the value of 1.
4. While the queue is not empty, follow these steps:
   1. Pop the first cell from the queue.
   2. If the popped cell is the destination cell, return the shortest distance.
   3. Otherwise, mark the cell as visited, and explore all the valid neighbors of the cell.
   4. Add each valid neighbor of the cell to the queue with the increased distance.

Pseudo code:

function shortestPathBinaryMatrix(matrix): if matrix[0][0] == 1: return -1

queue = Queue()
visited = set()
queue.append((0, 0, 1))
visited.add((0, 0))

while queue:
    row, col, distance = queue.popleft()
    if row == len(matrix)-1 and col == len(matrix[0])-1:
        return distance
    for dx, dy in [(0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1),(-1,1),(-1,-1)]:
        new_row, new_col = row+dx, col+dy
        if new_row < 0 or new_col < 0 or new_row >= len(matrix) or new_col >= len(matrix[0]) or matrix[new_row][new_col] == 0 or (new_row, new_col) in visited:
            continue
        visited.add((new_row, new_col))
        queue.append((new_row, new_col, distance+1))

return -1

The time complexity of this algorithm is O(n^2) where n is the length of sides of the matrix. This is because we visit each cell only once and the queue size is at most n^2. The space complexity of this algorithm is also O(n^2) because of the visited matrix and the queue.

1