Leetcode 934. Shortest Bridge

Let's understand what we're being asked to do. We have an n×n binary grid (containing only 0s and 1s) with exactly two separate islands. An island is a group of 1s connected horizontally or vertically (4-connected).

For example, given:

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

We have island 1 at position (0,1) and island 2 at position (2,2). They are separated by water (0s).

Our goal: Find the minimum number of 0→1 flips needed to connect these two islands. In the example above, we could flip (1,1) and (1,2) to create a bridge, requiring 2 flips.

Important constraints: The grid contains exactly two 4-connected islands (no more, no less). We need to find the shortest bridge between them.

Edge cases to consider: What if the islands are already adjacent (answer would be 0)? What if the grid is very large? What's the most efficient way to measure distance between island boundaries?

The brute force approach would be to identify all cells belonging to each island using DFS/BFS, then check every pair of cells (one from island 1, one from island 2) and calculate their Manhattan distance. The minimum distance minus 1 would be the answer (since adjacent cells have distance 1 but need 0 flips). This requires iterating through all possible pairs of cells from the two islands.

def shortest_bridge(grid):
    """
    Brute force: Find all cells of both islands using DFS,
    then check every pair of cells (one from each island)
    to find minimum Manhattan distance.
    """
    n = len(grid)
    
    # Find all cells belonging to island 1
    island1 = []
    # Find all cells belonging to island 2
    island2 = []
    
    visited = [[False] * n for _ in range(n)]
    
    def dfs(r, c, island):
        """DFS to collect all cells of an island"""
        if r < 0 or r >= n or c < 0 or c >= n:
            return
        if visited[r][c] or grid[r][c] == 0:
            return
        
        visited[r][c] = True
        island.append((r, c))
        
        # Explore all 4 directions
        dfs(r + 1, c, island)
        dfs(r - 1, c, island)
        dfs(r, c + 1, island)
        dfs(r, c - 1, island)
    
    # Find first island
    found_first = False
    for i in range(n):
        if found_first:
            break
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j, island1)
                found_first = True
                break
    
    # Find second island
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1 and not visited[i][j]:
                dfs(i, j, island2)
    
    # Brute force: check every pair of cells
    min_distance = float('inf')
    
    for r1, c1 in island1:
        for r2, c2 in island2:
            # Manhattan distance between two cells
            distance = abs(r1 - r2) + abs(c1 - c2)
            min_distance = min(min_distance, distance)
    
    # Subtract 1 because adjacent cells have distance 1 but need 0 flips
    return min_distance - 1

The key insight is that we need to find the shortest path from any cell of island 1 to any cell of island 2. This is not about connecting specific points - it's about connecting the boundaries of two regions.

Think of it as: "What's the minimum distance between the two island perimeters?" We need to expand outward from one island until we touch the other.

If we tried checking every pair of cells (one from each island), we'd have O(n⁴) comparisons for an n×n grid. That's extremely inefficient!

Instead, by treating all cells of one island as simultaneous starting points and expanding outward level-by-level, we naturally find the shortest bridge. The first time we reach the other island tells us the minimum distance.

Imagine you're standing on island 1 and you have unlimited paint. You paint all cells of island 1 first. Then, in round 1, you paint all water cells adjacent to island 1. In round 2, you paint all water cells adjacent to those. You keep expanding outward in waves.

The moment your paint touches island 2, you know the number of rounds equals the minimum bridge length. This wave-like expansion is exactly what breadth-first search does - it explores all cells at distance d before exploring cells at distance d+1.

The optimal approach uses a two-phase BFS strategy. First, use DFS or BFS to mark all cells of one island (say, island 1) and add them all to a queue as starting points. Then, perform multi-source BFS from all cells of island 1 simultaneously, expanding outward across water cells level by level. Track the number of levels (distance) as we expand. The moment we reach any cell of island 2, the current level count is our answer - this represents the minimum number of 0→1 flips needed to bridge the islands.

from collections import deque
def shortest_bridge(grid):
    """
    Find the shortest bridge between two islands in a binary grid.
    Uses DFS to mark first island, then multi-source BFS to find shortest path to second island.
    """
    n = len(grid)
    
    # Find first island cell
    def find_first_island():
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    return (i, j)
        return None
    
    # DFS to mark all cells of first island and add to queue
    def dfs(i, j, queue):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
            return
        grid[i][j] = 2  # Mark as visited (first island)
        queue.append((i, j))
        dfs(i + 1, j, queue)
        dfs(i - 1, j, queue)
        dfs(i, j + 1, queue)
        dfs(i, j - 1, queue)
    
    # Initialize queue with all cells of first island
    queue = deque()
    start_i, start_j = find_first_island()
    dfs(start_i, start_j, queue)
    
    # Multi-source BFS from first island
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    distance = 0
    
    while queue:
        size = len(queue)
        for _ in range(size):
            i, j = queue.popleft()
            
            for di, dj in directions:
                ni, nj = i + di, j + dj
                
                if ni < 0 or ni >= n or nj < 0 or nj >= n or grid[ni][nj] == 2:
                    continue
                
                # Found second island
                if grid[ni][nj] == 1:
                    return distance
                
                # Water cell - mark as visited and add to queue
                grid[ni][nj] = 2
                queue.append((ni, nj))
        
        distance += 1
    
    return -1

• Two-phase BFS strategy: When finding shortest paths between two unknown regions, use DFS/BFS to mark one region first, then multi-source BFS from that region's boundary - this transforms an ambiguous two-target problem into a clear single-target search with known starting points.
• Multi-source BFS for boundary expansion: Instead of starting BFS from a single point, initialize the queue with all boundary cells of the first island - this simultaneously expands in all directions and naturally finds the shortest path to any point on the second island, avoiding the need to try every possible starting point.
• Island marking with DFS: Use DFS to flood-fill the first island you encounter (changing 1s to 2s or adding to a set) - this prevents revisiting the same island during BFS and clearly distinguishes between the two islands, making the bridge-building phase unambiguous.
• Distance tracking without visited array: In BFS for shortest path, track distance as a level counter (incrementing after processing each queue level) rather than storing distance in each cell - this saves space and the queue naturally prevents revisiting cells when you mark them as visited upon addition, not upon removal.
• Early termination on first contact: The BFS can return immediately upon reaching any cell of the second island (a cell with value 1) - because BFS explores layer by layer, the first contact is guaranteed to be the shortest bridge, eliminating the need to explore all possibilities.
• Grid boundary problems pattern: This island-bridging technique applies to any problem requiring minimum connections between separated regions in a grid - think of it for problems involving connecting components, expanding territories, or finding shortest paths between multiple sources and targets in 2D spaces.