LeetCode Solutions Blog

Number of Closed Islands

Difficulty: Medium

Problem Description

Given a 2D grid consisting 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 surrounded by 1s. Return the number of closed islands.

Key Insights

A closed island is surrounded on all sides by water (1s).
The task can be approached using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the grid.
We need to mark visited land cells to avoid counting them multiple times.
Any land cell that touches the boundary of the grid cannot be part of a closed island.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of rows and M is the number of columns in the grid. We potentially visit each cell once.

Space Complexity: O(N * M) in the worst case for the recursion stack in DFS or the queue in BFS, plus O(1) if we modify the grid in place.

Solution

The problem can be solved using Depth-First Search (DFS). We will iterate through each cell in the grid. When we find a land cell (0), we will check if it forms a closed island by performing a DFS. If during our DFS we reach the boundary of the grid, we know that the island is not closed. Otherwise, we increment our count of closed islands.

Code Solutions

def closedIsland(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    
    def dfs(r, c):
        # If we reach the boundary of the grid, return False
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        # If we hit water (1), return True
        if grid[r][c] == 1:
            return True
        
        # Mark the cell as visited by setting it to 1 (water)
        grid[r][c] = 1
        
        # Perform DFS in all four directions
        up = dfs(r - 1, c)
        down = dfs(r + 1, c)
        left = dfs(r, c - 1)
        right = dfs(r, c + 1)
        
        # Return True if all four sides are connected to water
        return up and down and left and right
        
    closed_islands = 0
    
    # First, we mark all the cells connected to the boundary
    for i in range(rows):
        for j in range(cols):
            if (i == 0 or i == rows - 1 or j == 0 or j == cols - 1) and grid[i][j] == 0:
                dfs(i, j)
    
    # Now, count the closed islands
    for i in range(1, rows - 1):
        for j in range(1, cols - 1):
            if grid[i][j] == 0:  # Found a new closed island
                if dfs(i, j):  # Check if this island is closed
                    closed_islands += 1
    
    return closed_islands