Shortest Bridge Interview Question for Meta

## Problem: Shortest Bridge

You are given an `n x n` binary matrix `grid` where `1` represents land and `0` represents water. An **island** is a 4-directionally connected group of `1`'s not connected to any other `1`'s. There are **exactly two islands** in `grid`. You may change `0`'s to `1`'s to connect the two islands to form **one island**. Return *the smallest number of* `0`*'s you must flip to connect the two islands*.

## Naive Approach

A naive approach would involve iterating through every cell in the grid, and for each `0`, check if it connects the two islands. This would involve performing a BFS or DFS from each `0` to see if it can reach both islands.  This is highly inefficient.

## Optimal Solution

The optimal solution involves the following steps:

1.  **Identify the first island:** Use DFS to find all the cells belonging to the first island and mark them as visited. Store these cells in a queue.
2.  **BFS to find the shortest path:** Perform a BFS starting from the cells of the first island. In each step, expand the search by one layer of cells. If we encounter a cell belonging to the second island, we have found the shortest path. The number of steps taken is the shortest distance between the two islands.

```python
from collections import deque

def shortestBridge(grid):
    n = len(grid)
    visited = set()

    # Function to perform DFS to find the first island
    def dfs(i, j):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] == 0 or (i, j) in visited:
            return
        visited.add((i, j))
        return [(i,j)] + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)
    

    # Find the first island using DFS
    first_island = None
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                first_island = dfs(i, j)
                break
        if first_island:
            break
    
    # BFS to find the shortest bridge
    queue = deque(first_island)
    distance = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        size = len(queue)
        for _ in range(size):
            i, j = queue.popleft()
            
            for di, dj in directions:
                new_i, new_j = i + di, j + dj
                
                if 0 <= new_i < n and 0 <= new_j < n and (new_i,new_j) not in visited:
                    if grid[new_i][new_j] == 1:
                        return distance
                    
                    queue.append((new_i, new_j))
                    visited.add((new_i, new_j))
        distance += 1
    return -1 # Should not happen as there are exactly two islands

# Example Usage
grid1 = [[0,1],[1,0]]
print(f"Shortest bridge for grid1: {shortestBridge(grid1)}")

grid2 = [[0,1,0],[0,0,0],[0,0,1]]
print(f"Shortest bridge for grid2: {shortestBridge(grid2)}")

grid3 = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
print(f"Shortest bridge for grid3: {shortestBridge(grid3)}")

Big(O) Time Complexity Analysis

DFS (Finding the first island): O(n^2) in the worst case, where n is the size of the grid. This is because we might have to visit every cell in the grid if the first island covers a large portion of it.
BFS (Finding the shortest bridge): O(n^2) in the worst case. In the worst-case scenario, the BFS might expand to cover the entire grid before finding the second island. Each cell is visited at most once because we keep track of visited cells using the visited set.

Therefore, the overall time complexity is O(n^2) + O(n^2) which simplifies to O(n^2).

Big(O) Space Complexity Analysis

DFS: O(n^2) in the worst case for the visited set, as the first island could potentially cover the entire grid. The recursion depth of DFS can also reach O(n) in the worst case (e.g., a long chain of connected cells), but since it's dominated by the size of the visited set, we consider this part to be less influential than the visited set.
BFS: O(n^2) in the worst case for the queue. In the worst case, the queue might contain all the cells of the grid (especially if the first island is large and near the center).

Therefore, the overall space complexity is O(n^2) + O(n^2), which simplifies to O(n^2).

Edge Cases

Grid with only one island: The problem statement specifies that there are exactly two islands. If there's only one, the algorithm will still execute. The BFS will complete without finding a second island, and the function will return -1. While this violates the problem's constraints, handling this case requires extra validation at the beginning, which might not be necessary during an interview. The core algorithm remains functional in the context of the problem statement.
Disconnected islands sharing an edge or corner: The islands are defined as 4-directionally connected. If two islands touch only at a corner, they are still considered separate islands. The algorithm will correctly calculate the shortest bridge as 1 in this case (filling the 0 between them).
Large Islands vs. Small Islands: The size of the islands doesn't affect the time complexity, which remains O(n^2) because the DFS and BFS will visit cells relative to grid size. However, large islands can lead to larger queues and visited sets, thus affecting space complexity, but remaining O(n^2).
Islands very close together: If the islands are very close to each other, the BFS will terminate quickly. The time complexity is still O(n^2) in the worst case, but the actual execution time will be much lower.