Leetcode 1254. Number of Closed Islands

Problem statement

https://leetcode.com/problems/number-of-closed-islands/

Solution

First, start with borders and sink all land we can reach. Then traverse once again, using classical number of islands problem.

Complexity

It is O(mn) for time and space.

Code

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

        def dfs(i, j):
            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != 0:
                return
            grid[i][j] = -1
            for x, y in [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]:
                dfs(x, y)
        
        for i, j in product(range(m), range(n)):
            if grid[i][j] == 0:
                dfs(i, j)
                cnt += 1
                
        return cnt