Shortest Bridge — DFS Find + BFS Expand

Problem

Given a binary matrix with exactly two islands, return the minimum number of 0s to flip to connect them.

Approach — DFS then BFS

DFS: Find any cell of island 1, flood-fill all of island 1, adding all its cells to BFS queue
BFS: Expand outward from island 1; first time we hit island 2, return distance

Time: O(n²) | Space: O(n²)

Solutions

Python

from collections import deque
class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n=len(grid)
        q=deque(); found=False
        def dfs(r,c):
            if not(0<=r<n and 0<=c<n) or grid[r][c]!=1: return
            grid[r][c]=2; q.append((r,c))
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]: dfs(r+dr,c+dc)
        for r in range(n):
            if found: break
            for c in range(n):
                if grid[r][c]==1:
                    dfs(r,c); found=True; break
        steps=0
        while q:
            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[nr][nc]==1: return steps
                        if grid[nr][nc]==0:
                            grid[nr][nc]=2; q.append((nr,nc))
            steps+=1
        return steps

Complexity

Time: O(n²) | Space: O(n²)