Space
Open
Interview
From Fieldwork
Scales
Archive
Phase 1: Identification (DFS)
Iterate through the grid until you find the first cell of land (1).
Use DFS to visit every connected cell of this island.
Mark these cells as visited (e.g., change them to 2 or adding them to a visited set) and add them to a queue for the next phase.
Crucial optimization: This creates a Multi-source BFS starting point. We don't start from one corner of the island; we start from the entire shoreline simultaneously.
Phase 2: The Bridge (BFS)
Process the queue layer by layer (like expanding ripples in a pond).
Each step moves 1 unit of distance away from Island A into the water (0).
The moment you touch a 1 that isn't part of Island A... Stop! You've hit Island B.
The number of layers you expanded is the length of the shortest bridge.
class Solution:
def shortestBridge(self, grid: list[list[int]]) -> int:
n = len(grid)
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visit = set()
q = deque()
# Helper: DFS to find the first island completely
def dfs(r, c):
if (r < 0 or c < 0 or r >= n or c >= n or
grid[r][c] == 0 or (r, c) in visit):
return
visit.add((r, c))
q.append((r, c)) # Add to queue for BFS later
for dr, dc in directions:
dfs(r + dr, c + dc)
# 1. FIND THE FIRST ISLAND
found = False
for r in range(n):
if found: break
for c in range(n):
if grid[r][c] == 1:
dfs(r, c)
found = True
break
# 2. BFS TOWARD THE SECOND ISLAND
res = 0
while q:
# Process entire layer (level-by-level)
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
if (nr, nc) in visit:
continue
if grid[nr][nc] == 1:
return res # Found the second island!
# Use the set to mark water as visited so we don't loop
visit.add((nr, nc))
q.append((nr, nc))
# Increment distance after finishing a full layer of expansion
res += 1
return -1Practice bench
Drafts stay on this device.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode