October 25Medium

Number of closed islands

Array
DFS
BFS
Union-Find
Matrix

Problem

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Solution

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = {}
        def dfs(i, j):
            res[(i,j)] = None
            for dx, dy in (-1,0),(1,0),(0,1),(0,-1):
                x, y = dx + i, dy + j
                if x < 0 or x >= m or y < 0 or y >= n:
                    res[(i,j)] = False
                    return False
                if grid[x][y] == 0:
                    if (x,y) in res:
                        if res[(x,y)] is False:
                            res[(i,j)] = False
                            return False
                    elif not dfs(x,y):
                        res[(i,j)] = False
                        return False
            res[(i,j)] = True
            return True

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and (i,j) not in res and dfs(i,j):
                    count += 1
        return count