Skip to content

934. Shortest Bridge

On LeetCode ->

Problem

Given an \(n \times n\) binary grid containing exactly two 4-directionally connected islands, return the minimum number of water cells to flip so the islands become connected.

[[0, 1],
 [1, 0]] -> 1

Key trick

Mark every cell of one island and use all of them as sources for BFS; the first time BFS reaches the other island, the current distance is the minimum number of flips.

Trap

  • Starting BFS from only one island cell instead of its entire boundary or component.
  • Counting the destination island as a flip.
  • Marking water only when dequeued, which allows duplicate queue entries.
  • Using recursive DFS in Python, since an island may contain \(10^4\) cells and exceed the recursion limit.

Why is it interesting?

It combines connected-component discovery with multi-source BFS, reducing a geometric connection problem to an unweighted shortest-path problem.

Python solution

from collections import deque


class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n = len(grid)
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        # Find any cell belonging to the first island.
        start = next(
            (r, c)
            for r in range(n)
            for c in range(n)
            if grid[r][c] == 1
        )

        # Mark the first island and make all its cells BFS sources.
        q = deque()
        stack = [start]
        grid[start[0]][start[1]] = 2

        while stack:
            r, c = stack.pop()
            q.append((r, c))

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    stack.append((nr, nc))

        flips = 0

        # Expand through water one layer at a time.
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if not (0 <= nr < n and 0 <= nc < n):
                        continue

                    # An unmarked land cell belongs to the second island.
                    if grid[nr][nc] == 1:
                        return flips

                    if grid[nr][nc] == 0:
                        grid[nr][nc] = 2
                        q.append((nr, nc))

            flips += 1

        return -1

Time complexity: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Comment on my solution

  • q is never populated, so the BFS loop never executes.
  • Grid water cells are integers, but the code compares them with the string "0".
  • After discovering (nr, nc), it enqueues (r, c) instead of the neighbor.
  • Simultaneously expanding both islands while using one flips counter does not correctly measure longer bridges.
  • The recursive DFS can exceed Python's recursion limit on a large island.
  • Marking only one island is simpler: every remaining 1 then unambiguously belongs to the destination island.
# Ideas:
# - multi BFS sources starting on 1 already on the grid
#   - flip zero, and enque
# - mark cell with "a" for first island
# - mark cell with "b" for second island

from collections import deque

# WRONG
class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n = len(grid)
        q = deque()

        def dfs(r,c,island):
            grid[r][c] = island
            for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < n) and (0 <= nc < n) and grid[nr][nc] == 1:
                    dfs(nr,nc,island)

        island = "a"
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    dfs(r,c,island)
                    island = "b"

        flips = 0

        while q:
            flips += 1
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in ((-1,0), (1,0), (0,-1), (0,1)):
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < n) and (0 <= nc < n):
                        if grid[r][c] == "a":
                            if grid[nr][nc] == "b":
                                return flips
                            elif grid[nr][nc] == "0":
                                grid[nr][nc] = "a"
                                q.append((r,c))
                        elif grid[r][c] == "b":
                            if grid[nr][nc] == "a":
                                return flips
                            elif grid[nr][nc] == "0":
                                grid[nr][nc] = "b"
                                q.append((r,c))