LeetCode 1254 - Number of Closed Islands

This problem provides a 2D grid representing a map of land and water. Cells with 0 represent land, and cells with 1 repr

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 1254

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

This problem provides a 2D grid representing a map of land and water. Cells with 0 represent land, and cells with 1 represent water. An island is any contiguous region of land connected horizontally or vertically (not diagonally). A closed island is an island that is entirely surrounded by water on all four sides, including edges of the grid.

The task is to count how many closed islands exist in the given grid. The input grid can be as large as 100 by 100, meaning a naive algorithm must be efficient enough to handle up to 10,000 cells. The problem guarantees that each cell is either 0 or 1, so we do not need to handle invalid cell values.

Important edge cases include grids where islands touch the grid edges (they cannot be closed), grids entirely filled with water (no islands), and single-cell grids that may or may not form a closed island.

Approaches

The brute-force approach is to iterate over every land cell (0) and perform a depth-first search (DFS) or breadth-first search (BFS) to explore the entire connected island. While exploring, we track whether any part of the island touches the border of the grid. If it does, we mark it as not closed; otherwise, we count it. This approach works but may repeatedly traverse the same cells unnecessarily, and if not carefully implemented, it could use extra space for visited cells.

The optimal approach leverages the observation that any island touching the border cannot be closed. We first flood-fill all land cells connected to the border, marking them as visited or water to ignore them. After this pre-processing step, we iterate over the remaining land cells. Each DFS/BFS from these cells is guaranteed to be a closed island. This reduces unnecessary checks and simplifies logic.

Approach Time Complexity Space Complexity Notes
Brute Force O(m*n) O(m*n) Explore every land cell; track visited cells; check borders during DFS/BFS
Optimal O(m*n) O(m*n) Pre-flood-fill border-connected land; remaining islands are all closed

Algorithm Walkthrough

  1. Iterate through all border cells of the grid (top row, bottom row, leftmost column, rightmost column). For each land cell (0), perform DFS to mark all connected land as visited or converted to water (1). This ensures that no border-connected island will be counted later.
  2. Initialize a counter closed_islands = 0.
  3. Iterate over all cells of the grid. For each unvisited land cell (0), perform DFS to mark all connected land as visited and increment the closed_islands counter by one.
  4. Return closed_islands as the total number of closed islands.

Why it works: The invariant maintained is that all islands touching the grid edges are removed before counting. Therefore, any remaining land island is fully enclosed by water and meets the closed island definition. DFS ensures all connected land cells are visited in each step, guaranteeing that no island is counted multiple times.

Python Solution

from typing import List

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        def dfs(r: int, c: int):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 1:
                return
            grid[r][c] = 1
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)
        
        # Flood-fill border-connected lands
        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
        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

Explanation: The dfs function marks all connected land cells as water to avoid recounting. First, all border-connected land cells are removed, ensuring only potential closed islands remain. The nested loops then search for remaining land cells and count each isolated DFS as a closed island.

Go Solution

func closedIsland(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 1 {
            return
        }
        grid[r][c] = 1
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    }

    // Flood-fill border-connected lands
    for r := 0; r < rows; r++ {
        dfs(r, 0)
        dfs(r, cols-1)
    }
    for c := 0; c < cols; c++ {
        dfs(0, c)
        dfs(rows-1, c)
    }

    closedIslands := 0
    for r := 1; r < rows-1; r++ {
        for c := 1; c < cols-1; c++ {
            if grid[r][c] == 0 {
                dfs(r, c)
                closedIslands++
            }
        }
    }
    return closedIslands
}

Explanation: Go handles slices and DFS similarly to Python. The function uses recursion to mark visited land cells. Go does not require type hints for inner functions, and the indexing and loop logic remain consistent with the Python approach.

Worked Examples

Example 1:

Grid:
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

Step 1: Flood-fill border lands converts the rightmost column of 0s to 1.

Step 2: DFS iterates from internal cells. The first internal island (top-left) is counted as closed. The second internal island (bottom-left) is counted as closed.

Output: 2

Example 2:

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

Border DFS removes top-left and top-right land touching the borders. One central island remains.

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Each cell is visited at most once during DFS flood-fill and counting.
Space O(m*n) Recursive DFS stack may grow up to the size of the largest island in the worst case.

The algorithm is efficient for the given constraints since it processes each cell a constant number of times. Recursive stack depth is limited by the island size.

Test Cases

# Provided examples
assert Solution().closedIsland([[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]]) == 2
assert Solution().closedIsland([[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]) == 1
assert Solution().closedIsland([[1,1,1,1,1,1,1],[1,0,0,0,0,0,1],[1,0,1,1,1,0,1],[1,0,1,0,1,0,1],[1,0,1,1,1,0,1],[1,0,0,0,0,0,1],[1,1,1,1,1,1,1]]) == 2

# Edge cases
assert Solution().closedIsland([[1]]) == 0  # single water
assert Solution().closedIsland([[0]]) == 0  # single land on border, not closed
assert Solution().closedIsland([[1,1,1],[1,0,1],[1,1,1]]) == 1  # 1 closed island inside border
assert Solution().closedIsland([[0,0,0],[0,0,0],[0,0,0]]) == 0  # all land touches borders
assert Solution().closedIsland([[1,1,1],[1,1,1],[1,1,1]]) == 0  # all water
Test Why
Example 1 Multiple closed islands with some islands touching borders
Example 2 Single central closed island
Example 3 Multiple islands fully enclosed
Single water cell Minimal grid with no