1254. Number of Closed Islands

Problem Description

Given a 2D grid representing land (0) and water (1), find the number of closed islands. A closed island is a maximal 4-directionally connected group of 0s (land) completely surrounded by 1s (water).

Solutions

Two approaches are presented: Depth-First Search (DFS) and Union-Find.

Solution 1: Depth-First Search (DFS)

This approach uses DFS to identify and count closed islands.

Algorithm:

1. Iterate: Traverse the grid.
2. DFS Function: For each cell with value 0 (land), call a recursive DFS function.
   • Mark the current cell as visited (change its value to 1).
   • Recursively call DFS on its four neighbors (up, down, left, right) if they are land (0).
3. Boundary Check: The DFS function returns true if the island is closed (completely surrounded by water), and false otherwise. This is determined by checking if any visited land cell is on the boundary of the grid.
4. Count Islands: Increment the count of closed islands if the DFS function returns true.

Time Complexity: O(M * N), where M and N are the dimensions of the grid. Each cell is visited at most once. Space Complexity: O(M * N) in the worst case, due to the recursive call stack during DFS (depth of recursion can be at most M*N).

Code (Python):

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i, j):
            if not (0 <= i < m and 0 <= j < n and grid[i][j] == 0):
                return False  # Out of bounds or water
            grid[i][j] = 1 # Mark as visited (water)
            is_closed = True
            is_closed &= dfs(i + 1, j)
            is_closed &= dfs(i - 1, j)
            is_closed &= dfs(i, j + 1)
            is_closed &= dfs(i, j - 1)
            return is_closed
 
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    if dfs(i, j):
                        count += 1
        return count

Solution 2: Union-Find

This approach uses a Union-Find data structure to efficiently group connected land cells.

Algorithm:

1. Union-Find Setup: Create a Union-Find data structure to represent the connectivity of land cells.
2. Initial Unions: Iterate through the grid. For cells on the boundary that are land (0), unite them with a virtual "boundary" node. This ensures that islands touching the boundary are not considered closed.
3. Internal Unions: For land cells that are not on the boundary, unite them with their adjacent land cells (up, down, left, right).
4. Count Closed Islands: Iterate through the grid again. If a land cell's root (in the Union-Find) is the cell itself (not united with the boundary), it represents a closed island. Increment the count accordingly.

Time Complexity: O(M * N * α(M * N)), where α is the inverse Ackermann function, which grows extremely slowly and can be considered practically constant for all realistic input sizes. The dominant operation is the union and find operations in the Union-Find data structure. Space Complexity: O(M * N) to store the Union-Find data structure.

Code (Python):

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
 
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
 
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.size[root_i] < self.size[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            self.size[root_i] += self.size[root_j]
 
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m * n + 1) # +1 for the boundary node
        boundary_node = m * n
 
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                        uf.union(i * n + j, boundary_node)
                    else:
                        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                            if grid[x][y] == 0:
                                uf.union(i * n + j, x * n + y)
 
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and uf.find(i * n + j) != boundary_node:
                    count += 1
        return count
 

Both solutions correctly solve the problem. The choice depends on the specific needs of the application. DFS is generally simpler to implement, while Union-Find might offer better performance for extremely large grids due to its amortized time complexity. However, the difference in performance is unlikely to be significant for most practical problem sizes.