Constraints

• 1 <= R, C <= 200
• grid[i][j] is either 0 or 1
• There are exactly two islands in the grid
• Cells are connected only in 4 directions: up, down, left, and right

Examples

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    queue = deque()

    def mark_first_island(sr, sc):
        stack = [(sr, sc)]
        visited[sr][sc] = True

        while stack:
            r, c = stack.pop()
            queue.append((r, c, 0))

            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if not visited[nr][nc] and grid[nr][nc] == 1:
                        visited[nr][nc] = True
                        stack.append((nr, nc))

    found = False
    for r in range(rows):
        if found:
            break
        for c in range(cols):
            if grid[r][c] == 1:
                mark_first_island(r, c)
                found = True
                break

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]:
                if grid[nr][nc] == 1:
                    return dist
                visited[nr][nc] = True
                queue.append((nr, nc, dist + 1))

    return -1

Time complexity: O(R * C). Space complexity: O(R * C).

Hints

1. First, find one of the islands and mark all of its cells.
2. Then run a multi-source BFS starting from every cell of that island at once. The first time you reach the other island gives the minimum number of flips.