Problem statement

https://binarysearch.com/problems/Sinking-Islands/

Solution

The idea is to add all border with values 1 to queue and pefrome bfs (or stack with dfs) and mark all visited nodes as 2. Then run once again, where we substitute all 1 with 0, our sinked islands and finally replace all 2 with 1.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, grid):
        n, m = len(grid[0]), len(grid)
        b1  = [(0, i) for i in range(n)]  + [(i, 0) for i in range(1, m)]
        b2 = [(m-1, i) for i in range(n)] + [(i, n-1) for i in range(m-1)]

        V = set()
        q = deque([(x, y) for x, y in b1 + b2 if grid[x][y] == 1])
        while q:
            i, j = q.popleft()
            grid[i][j] = 2
            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] != 1 or (x, y) in V: continue
                V.add((x, y))
                q += [(x, y)]

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

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

        return grid