We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Closed Islands

Number: 1380

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon

Problem Description

Given a 2D grid consisting of 0s (land) and 1s (water), an island is defined as a maximal group of 0s connected 4-directionally. A "closed island" is an island that is completely surrounded by water (i.e., all its boundaries—left, top, right, bottom—are water). The task is to count the number of closed islands in the grid.

Key Insights

  • Flood-fill (using DFS/BFS) can be used to traverse and "sink" islands.
  • First, eliminate islands connected to the grid border because they cannot be closed.
  • Then, iterate over the inner grid cells and count islands that are completely surrounded by water.
  • Time complexity is O(m*n) where m and n are the grid dimensions.
  • Space complexity depends on recursion depth or queue used in traversal, which in worst-case is O(m*n).

Space and Time Complexity

Time Complexity: O(mn)
Space Complexity: O(mn) (in worst-case, for the recursion stack or BFS queue)

Solution

Use Depth-First Search (DFS) to traverse the grid. The algorithm has two main phases. In the first phase, iterate over the border cells and perform DFS on any cell that is a land (0) to mark all reachable land cells as water (1). This ensures that we do not count islands that are connected to the border. In the second phase, iterate over the entire grid (ignoring the borders) and perform DFS on any remaining land cell. Each DFS call here represents one closed island and increments the count. Mark all visited cells during DFS to avoid recounting.

Code Solutions

# Python solution using DFS

def closedIsland(grid):
    # Get grid dimensions
    rows, cols = len(grid), len(grid[0])
    
    # Helper function: DFS to sink connected land cells
    def dfs(r, c):
        # If out of bounds or cell is water, return immediately
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 1:
            return
        # Mark the cell as water to indicate it is visited (sink it)
        grid[r][c] = 1
        # Recursively call dfs on all 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    # Eliminate border islands by sinking all land connected to the borders
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)
    
    closed_islands = 0
    # Count closed islands by iterating over inner grid cells
    for r in range(1, rows - 1):
        for c in range(1, cols - 1):
            if grid[r][c] == 0:
                dfs(r, c)
                closed_islands += 1
                
    return closed_islands

# Example usage:
grid_example = [
    [1,1,1,1,1,1,1,0],
    [1,0,0,0,0,1,1,0],
    [1,0,1,0,1,1,1,0],
    [1,0,0,0,0,1,0,1],
    [1,1,1,1,1,1,1,0]
]
print(closedIsland(grid_example))  # Output: 2
← Back to All Questions