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
- First find one island with a DFS and mark it (e.g. as
2), collecting its cells into a BFS queue. - Then run a multi-source BFS from every cell of that island, expanding through water.
- The number of expansion layers before touching the other island is the bridge length.
- 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.