Problem Description

You are given a 2D grid consisting of 0s (representing land) and 1s (representing water). An island is defined as a group of 0s that are connected horizontally or vertically (4-directionally connected). A closed island is an island that is completely surrounded by water on all sides - meaning none of its land cells touch the boundary of the grid.

Your task is to count how many closed islands exist in the grid.

Key points to understand:

• Land cells are represented by 0 and water cells by 1
• Islands are formed by connecting adjacent land cells (up, down, left, right)
• A closed island must not have any land cells on the edges of the grid
• If any part of an island touches the boundary of the grid, it is NOT a closed island

For example, if you have a land cell at position (0, 5) (on the top edge) or (3, 0) (on the left edge), any island containing these cells would not be closed since they touch the boundary.

The function should return the total number of closed islands in the grid.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The 2D grid can be viewed as a graph where each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. We need to explore connected components of land cells (0s).

Is it a tree?

• No: The grid structure is not a tree. It's a general graph that can have multiple connected components (islands) and doesn't have a hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The grid represents an undirected graph where connections between adjacent cells are bidirectional.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between points. We're identifying and counting connected components (islands) that meet specific criteria.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to find connected groups of land cells (islands) and determine if they're completely surrounded by water.

Does the problem have small constraints?

• Yes: While not explicitly stated, grid problems typically have manageable constraints that allow for DFS/BFS traversal of all cells.

DFS/backtracking?

• Yes: DFS is perfect for exploring all connected land cells from a starting point to identify complete islands.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem. DFS allows us to:

1. Explore each connected component of land cells completely
2. Mark visited cells to avoid counting the same island multiple times
3. Check if any cell in the component touches the boundary (making it not closed)
4. Count only those islands that are completely surrounded by water

Intuition

The key insight is to think of this problem as finding connected components with a special property - they must not touch the grid's boundary.

When we encounter a land cell (0), we know it's part of an island. The question is: is this island closed? To determine this, we need to explore the entire island and check if any of its cells are on the boundary of the grid.

Here's the thought process:

1. Why DFS? When we find a land cell, we need to explore all connected land cells to map out the complete island. DFS naturally follows paths to their end, making it perfect for exploring connected components.

2. The boundary check trick: Instead of collecting all cells of an island and then checking if any touch the boundary, we can be clever. During our DFS traversal, we track whether we're visiting any boundary cells. If we visit a cell where i = 0 or i = m-1 (top/bottom edge) or j = 0 or j = n-1 (left/right edge), we know this island is NOT closed.

3. Marking visited cells: To avoid counting the same island multiple times, we can modify the grid itself. When we visit a land cell (0), we change it to water (1). This serves two purposes:

   • Prevents revisiting the same cell
   • Ensures we don't count the same island twice

4. The AND operation insight: The solution uses a clever &= operation to track if an island is closed. We start assuming the current cell could be part of a closed island (return 1 if it's not on boundary). As we explore neighbors recursively, if ANY neighbor indicates the island touches the boundary (returns 0), the AND operation ensures our result becomes 0, marking the entire island as not closed.

5. Counting strategy: We iterate through every cell in the grid. When we find an unvisited land cell (0), we run DFS. If DFS returns 1 (island is closed), we increment our count. If it returns 0 (island touches boundary), we don't count it.

The beauty of this approach is that it handles everything in a single pass through the grid, marking cells as we go to avoid redundant work.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

Following the DFS approach identified earlier, let's walk through the implementation step by step:

1. Main Function Structure: We iterate through every cell in the grid. When we find a land cell (0), we call our DFS function to explore the entire island. The DFS returns whether the island is closed or not.

sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))

This line cleverly counts closed islands - it only adds 1 to the sum when both conditions are true: the cell is land (grid[i][j] == 0) AND the DFS confirms it's a closed island (dfs(i, j) returns 1).

2. DFS Implementation: The DFS function explores an island starting from position (i, j) and determines if it's closed.

def dfs(i: int, j: int) -> int:
    res = int(0 < i < m - 1 and 0 < j < n - 1)
    grid[i][j] = 1
    # ... explore neighbors
    return res

3. Boundary Check: The crucial line res = int(0 < i < m - 1 and 0 < j < n - 1) checks if the current cell is NOT on the boundary:

• 0 < i < m - 1: Cell is not on top or bottom edge
• 0 < j < n - 1: Cell is not on left or right edge
• Returns 1 if it's an interior cell, 0 if it's on the boundary

4. Marking Visited Cells: grid[i][j] = 1 changes the land cell to water, preventing revisits and avoiding infinite recursion.

5. Exploring Neighbors: The solution uses a clever direction array technique:

dirs = (-1, 0, 1, 0, -1)
for a, b in pairwise(dirs):
    x, y = i + a, j + b

The pairwise(dirs) generates pairs: (-1, 0), (0, 1), (1, 0), (0, -1), representing the four directions (up, right, down, left).

6. Recursive Exploration with AND Logic:

if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
    res &= dfs(x, y)

For each valid neighboring land cell:

• We recursively call DFS
• Use &= (bitwise AND) to combine results
• If ANY cell in the island touches the boundary (returns 0), the entire result becomes 0
• Only if ALL cells are interior cells does the result remain 1

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 for the recursion stack when the entire grid is one island.

The elegance of this solution lies in how it combines the boundary check with the AND operation to propagate the "not closed" status throughout the entire island during the DFS traversal.

Example Walkthrough

Let's walk through a small example to illustrate how the solution works:

Grid:
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1

Step 1: Start iterating from position (0,0).

• (0,0) = 1 (water), skip
• (0,1) = 1 (water), skip
• Continue until we find land...

Step 2: At position (1,1), we find our first land cell (value = 0).

• Call dfs(1, 1)
• Check boundary: 0 < 1 < 4 AND 0 < 1 < 4 → Both true, so res = 1
• Mark (1,1) as visited by setting it to 1
• Explore neighbors:
  • Up (0,1): water, skip
  • Right (1,2): land! Call dfs(1, 2)
    • Boundary check: 0 < 1 < 4 AND 0 < 2 < 4 → res = 1
    • Mark (1,2) as visited
    • Explore its neighbors:
      • Up (0,2): water, skip
      • Right (1,3): land! Call dfs(1, 3)
        • Boundary check: 0 < 1 < 4 AND 0 < 3 < 4 → res = 1
        • Continue exploring...
      • Down (2,2): water, skip
      • Left (1,1): already visited (now water), skip
    • Return 1 (all connected cells are interior)
  • Down (2,1): land! Call dfs(2, 1)
    • Similar process, returns 1
  • Left (1,0): water, skip

Step 3: All recursive calls return 1, and we AND them together:

• res = 1 & 1 & 1 & 1 = 1
• This island is closed! Count = 1

Step 4: Continue iterating. All land cells from the first island are now marked as water (1), so we won't count them again.

The grid after processing the first island:

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Final Result: 1 closed island

Now let's see an example where an island is NOT closed:

Grid:
0 0 1 1
1 0 0 1
1 1 0 1
1 1 1 1

Step 1: At position (0,0), we find land.

• Call dfs(0, 0)
• Check boundary: 0 < 0 < 3 is FALSE (on top edge)
• So res = 0 (not closed!)
• Mark (0,0) as visited
• Explore neighbor (0,1):
  • Call dfs(0, 1)
  • Boundary check also fails: res = 0
  • Continue exploring (1,1)...

Step 2: Even though (1,1) is an interior cell and would return 1, the AND operation ensures:

• res = 0 & 1 & ... = 0

Result: This island touches the boundary, so it's not counted as a closed island.

The key insight: once ANY cell in an island touches the boundary (returns 0), the AND operation propagates this 0 throughout the entire island exploration, correctly identifying it as not closed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grid.

The algorithm visits each cell in the grid at most once. The main loop iterates through all m × n cells, and for each cell that contains a 0, it performs a DFS traversal. During the DFS, each cell is visited once and marked as 1 (visited), preventing revisits. The pairwise(dirs) operation generates 4 direction pairs, which is a constant operation. Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grid.

The space complexity is dominated by the recursion stack used in the DFS traversal. In the worst case, when the grid consists entirely of 0s forming a single connected component, the DFS could potentially traverse through all cells before backtracking, resulting in a recursion depth of O(m × n). This happens when the land forms a snake-like pattern through the entire grid. Additionally, the dirs variable uses constant space O(1), which doesn't affect the overall complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Grid

The solution modifies the input grid by marking visited cells as water (grid[i][j] = 1). This is destructive and changes the original data, which might be needed elsewhere or for multiple operations.

Problem Example:

# If you need to use the grid again after calling closedIsland
grid = [[0,0,1],[1,0,1],[1,1,1]]
result = solution.closedIsland(grid)
# grid is now modified - all 0s have become 1s!
# Any subsequent operation on grid will fail

Solution: Create a copy of the grid or use a separate visited set:

def closedIsland(self, grid: List[List[int]]) -> int:
    def dfs(row: int, col: int, visited: set) -> int:
        if (row, col) in visited:
            return 1
        visited.add((row, col))
      
        is_not_boundary = int(0 < row < rows - 1 and 0 < col < cols - 1)
      
        for i in range(4):
            next_row = row + directions[i]
            next_col = col + directions[i + 1]
          
            if (0 <= next_row < rows and 0 <= next_col < cols and 
                grid[next_row][next_col] == 0 and (next_row, next_col) not in visited):
                is_not_boundary &= dfs(next_row, next_col, visited)
      
        return is_not_boundary
  
    rows, cols = len(grid), len(grid[0])
    directions = [-1, 0, 1, 0, -1]
    visited_global = set()
    closed_island_count = 0
  
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 0 and (row, col) not in visited_global:
                visited_local = set()
                if dfs(row, col, visited_local):
                    closed_island_count += 1
                visited_global.update(visited_local)
              
    return closed_island_count

2. Incorrect Boundary Check Logic

A common mistake is checking if ANY cell is interior rather than ALL cells must be interior. Using OR logic instead of AND logic would give wrong results.

Wrong Approach:

# INCORRECT - using OR logic
res = int(0 < i < m - 1 and 0 < j < n - 1)
for neighbor in neighbors:
    res = res or dfs(neighbor)  # Wrong! This would mark island as closed if ANY cell is interior

Correct Approach: Always use AND logic (&=) to ensure ALL cells in the island are interior cells.

3. Stack Overflow for Large Islands

The recursive DFS can cause stack overflow for very large islands due to Python's recursion limit (default ~1000).

Solution: Use iterative DFS with an explicit stack:

def dfs_iterative(start_row: int, start_col: int) -> int:
    stack = [(start_row, start_col)]
    visited = set()
    is_closed = True
  
    while stack:
        row, col = stack.pop()
        if (row, col) in visited:
            continue
          
        visited.add((row, col))
        grid[row][col] = 1
      
        # Check if on boundary
        if not (0 < row < rows - 1 and 0 < col < cols - 1):
            is_closed = False
      
        # Add neighbors to stack
        for i in range(4):
            next_row = row + directions[i]
            next_col = col + directions[i + 1]
          
            if (0 <= next_row < rows and 0 <= next_col < cols and 
                grid[next_row][next_col] == 0 and (next_row, next_col) not in visited):
                stack.append((next_row, next_col))
  
    return int(is_closed)

4. Edge Case: Empty or Single-Cell Grid

The solution doesn't explicitly handle edge cases like empty grids or single-cell grids.

Solution: Add validation at the beginning:

if not grid or not grid[0]:
    return 0
if len(grid) <= 2 or len(grid[0]) <= 2:
    return 0  # No closed islands possible in grids smaller than 3x3