Shortest Path in Binary Matrix Interview Question for Meta

## Solution: Shortest Path in Binary Matrix

This problem asks us to find the shortest path from the top-left cell to the bottom-right cell in a binary matrix, where the path can only traverse cells with value 0 and must be 8-directionally connected. If no such path exists, we should return -1.

We can solve this problem using Breadth-First Search (BFS).

### 1. Naive (Brute Force) Solution

A brute-force approach would involve exploring all possible paths from the starting cell to the destination. This can be done using recursion or backtracking. However, this approach is highly inefficient due to the exponential number of possible paths and would likely result in a Time Limit Exceeded (TLE) error for larger matrices.

### 2. Optimal Solution (BFS)

We can use BFS to find the shortest path because BFS explores the graph layer by layer. This guarantees that the first path we find to the destination is the shortest one.

Here's the algorithm:

1.  **Initialization:**
    *   Check if the starting cell `grid[0][0]` or the ending cell `grid[n-1][n-1]` is 1. If either is 1, there's no clear path, so return -1.
    *   Initialize a queue with the starting cell `(0, 0)` and mark it as visited (e.g., by changing its value in the grid to 1).
    *   Initialize the path length to 1.
2.  **BFS Traversal:**
    *   While the queue is not empty:
        *   Get the size of the queue (number of nodes at the current level).
        *   Iterate through all nodes at the current level:
            *   Dequeue a cell `(row, col)` from the queue.
            *   If `(row, col)` is the destination cell `(n-1, n-1)`, return the current path length.
            *   Explore all 8 neighbors of `(row, col)`:
                *   For each neighbor `(new_row, new_col)`:
                    *   Check if the neighbor is within the grid boundaries, has a value of 0, and hasn't been visited yet.
                    *   If all conditions are met, enqueue the neighbor, mark it as visited (e.g., set `grid[new_row][new_col] = 1`), and continue the BFS.
        *   Increment the path length after processing all nodes at the current level.
3.  **No Path Found:** If the queue becomes empty and we haven't reached the destination, it means there's no clear path, so return -1.

```python
from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1

    queue = deque([(0, 0)])
    grid[0][0] = 1  # Mark as visited
    path_length = 1

    directions = [
        (0, 1), (0, -1), (1, 0), (-1, 0),
        (1, 1), (1, -1), (-1, 1), (-1, -1)
    ]

    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            row, col = queue.popleft()

            if row == n - 1 and col == n - 1:
                return path_length

            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 0:
                    queue.append((new_row, new_col))
                    grid[new_row][new_col] = 1  # Mark as visited

        path_length += 1

    return -1

# Example usage:
grid1 = [[0, 1], [1, 0]]
print(f"Shortest path for grid1: {shortestPathBinaryMatrix(grid1)}")  # Output: 2

grid2 = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]
print(f"Shortest path for grid2: {shortestPathBinaryMatrix(grid2)}")  # Output: 4

grid3 = [[1, 0, 0], [1, 1, 0], [1, 1, 0]]
print(f"Shortest path for grid3: {shortestPathBinaryMatrix(grid3)}")  # Output: -1

3. Big(O) Runtime Analysis

O(n^2): In the worst-case scenario, we might need to visit every cell in the grid. The BFS algorithm ensures that we visit each cell at most once. Therefore, the time complexity is proportional to the number of cells, which is n^2.

4. Big(O) Space Usage Analysis

O(n^2): In the worst-case scenario, the queue might contain all the cells in the grid (if all cells are 0 and form a clear path). The visited array (which we implement in-place by modifying the grid) also takes O(n^2) space. Therefore, the space complexity is O(n^2).

5. Edge Cases

Starting or Ending Cell is 1: As checked in the beginning, return -1 immediately.
Grid Size is 1x1: If the grid is just one cell, return 1 if the cell is 0, and -1 otherwise.
No Clear Path: The BFS will terminate when the queue is empty, indicating that there's no valid path. We return -1 in this case.
Disconnected Components: Even if the start and end are 0, there might be disconnected 0-cells that prevent a clear path. BFS handles this naturally.