Problem statement

https://leetcode.com/problems/shortest-bridge/

Solution

First, we need to find two islands, using dfs. Then we use bfs, where we put one island fully to queue and run it.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def shortestBridge(self, grid):
        m, n, num = len(grid), len(grid[0]), 2
        comps = defaultdict(list)
        
        def dfs(i, j, k):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != 1:
                return
            grid[i][j] = k
            comps[k] += [(i, j)]
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                dfs(x, y, k)

        for i, j in product(range(m), range(n)):
            if grid[i][j] == 1:
                dfs(i, j, num)
                num += 1

        V = set()
        q = deque([(-1, x, y) for x, y in comps[2]])
        while q:
            dist, i, j = q.popleft()
            if grid[i][j] == 3: return dist
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                if not 0 <= x < m or not 0 <= y < n or grid[x][y] == 2 or (x, y) in V: continue
                V.add((x, y))
                q += [(dist + 1, x, y)]