⚡Flashcard Drill➔
NeetCode #580LC-934MediumGraphs
← Back to All Problems

#580 · #934 · Shortest Bridge(最短的桥)

📌 Problem Statement & Constraints

You are given an n x n binary grid with exactly two islands. Return the shortest bridge length: the minimum number of 0s that must be flipped to 1 to connect the two islands. Constraints: 2 <= n <= 100.

💡 Core Algorithmic Approaches

  1. First find one island with a DFS and mark it (e.g. as 2), collecting its cells into a BFS queue.
  2. Then run a multi-source BFS from every cell of that island, expanding through water.
  3. The number of expansion layers before touching the other island is the bridge length.
  4. This is the standard "grow from the whole source set" pattern.

💻 Benchmark Python3 Implementation

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        from collections import deque
        n = len(grid)

        def dfs(r: int, c: int, q: deque) -> None:
            if not (0 <= r < n and 0 <= c < n) or grid[r][c] != 1:
                return
            grid[r][c] = 2                 # mark as part of island A
            q.append((r, c))
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                dfs(r + dr, c + dc, q)

        q = deque()
        found = False
        for i in range(n):
            if found:
                break
            for j in range(n):
                if grid[i][j] == 1:
                    dfs(i, j, q)           # collect island A into the queue
                    found = True
                    break

        dist = 0
        while q:
            for _ in range(len(q)):        # one BFS layer
                r, c = q.popleft()
                for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1:
                            return dist    # reached island B
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2
                            q.append((nr, nc))
            dist += 1
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): each cell is visited a constant number of times.
💾 Space Complexity
O(n^2) for the queue.

⚠️ Interview Pitfalls & Follow-ups

  • Starting the BFS from a single cell of island A: all its cells are sources, giving the true minimum.
  • Returning dist + 1: the layer counter already equals the number of flipped cells when island B is touched.
  • Forgetting to mark island A: the BFS could expand back into it.
  • Using a DFS for the whole search: it does not give the shortest bridge.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems