1254. Number of Closed Islands - Explanation

1. Depth First Search - I

Intuition

A closed island is a group of land cells (0s) that is completely surrounded by water (1s) and does not touch the grid boundary. The key observation is that any island touching the boundary cannot be closed. We use dfs to explore each island, and during exploration, if we ever go out of bounds, we know this island is not closed. We return a boolean indicating whether the entire island stayed within bounds.

Algorithm

Create a visited set to track explored cells.
For each unvisited land cell, start a dfs.
In the dfs:
- If out of bounds, return false (not closed).
- If the cell is water or already visited, return true (valid boundary).
- Mark the cell as visited.
- Recursively check all four neighbors, combining results with AND logic (all must be valid for the island to be closed).
If the dfs returns true for an island, increment the result counter.
Return the total count of closed islands.

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        visit = set()

        def dfs(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS:
                return 0  # False
            if grid[r][c] == 1 or (r, c) in visit:
                return 1  # True

            visit.add((r, c))
            res = True
            for dx, dy in directions:
                if not dfs(r + dx, c + dy):
                    res = False
            return res

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if not grid[r][c] and (r, c) not in visit:
                    res += dfs(r, c)

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given grid.

2. Depth First Search - II

Intuition

Instead of tracking whether each island is closed during dfs, we can first eliminate all islands that touch the boundary. By running dfs from every boundary land cell and marking those cells as water, we effectively remove all non-closed islands. After this preprocessing, any remaining land cells must belong to closed islands, so we simply count them.

Algorithm

Run dfs from every land cell on the grid boundary (first/last row and first/last column) to mark those cells as water (1).
This "sinks" all islands connected to the boundary.
Iterate through the interior cells of the grid.
For each unvisited land cell, run dfs to mark the entire island as visited and increment the count.
Return the count of closed islands.

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [0, 1, 0, -1, 0]

        def dfs(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS or grid[r][c] == 1:
                return
            grid[r][c] = 1
            for d in range(4):
                dfs(r + directions[d], c + directions[d + 1])

        for r in range(ROWS):
            dfs(r, 0)
            dfs(r, COLS - 1)
        for c in range(COLS):
            dfs(0, c)
            dfs(ROWS - 1, c)

        res = 0
        for r in range(1, ROWS - 1):
            for c in range(1, COLS - 1):
                if grid[r][c] == 0:
                    dfs(r, c)
                    res += 1
        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given grid.

3. Breadth First Search

Intuition

BFS provides an iterative alternative to dfs for exploring islands. Starting from a land cell, we use a queue to visit all connected land cells level by level. While exploring, if any neighbor would take us out of bounds, we know the island is not closed. We track this with a flag and only count the island if it never touched the boundary.

Algorithm

Create a visited array to track explored cells.
For each unvisited land cell, start a bfs.
Initialize a queue with the starting cell and a flag isClosed = true.
While the queue is not empty:
- Dequeue a cell and explore its four neighbors.
- If a neighbor is out of bounds, set isClosed = false (but continue bfs to mark all cells).
- If the neighbor is valid land and unvisited, mark it visited and add to queue.
After bfs completes, if isClosed is true, increment the result.
Return the total count of closed islands.

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        visit = set()
        res = 0

        def bfs(r, c):
            q = deque([(r, c)])
            visit.add((r, c))
            is_closed = True

            while q:
                x, y = q.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or ny < 0 or nx >= ROWS or ny >= COLS:
                        is_closed = False
                        continue
                    if grid[nx][ny] == 1 or (nx, ny) in visit:
                        continue
                    visit.add((nx, ny))
                    q.append((nx, ny))

            return is_closed

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0 and (r, c) not in visit:
                    res += bfs(r, c)

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given grid.

4. Disjoint Set Union

Intuition

We can model this problem using Union-Find (DSU). Each land cell belongs to a component, and we union adjacent land cells together. The trick is to also create a virtual "boundary" node. Whenever a land cell is on the boundary or adjacent to the grid edge, we union it with this boundary node. After processing, any land component that shares the same root as the boundary node is not closed. We count components whose root differs from the boundary node's root.

Algorithm

Create a DSU with size ROWS * COLS + 1, where index N = ROWS * COLS represents the boundary.
For each land cell, check its four neighbors:
- If the neighbor is out of bounds, union the cell with the boundary node N.
- If the neighbor is valid land, union the two cells.
Find the root of the boundary node.
Iterate through all land cells. If a cell is its own root (representative of a component) and that root differs from the boundary root, count it.
Return the count of distinct closed island components.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        N = ROWS * COLS
        def index(r, c):
            return r * COLS + c

        dsu = DSU(N)
        directions = [0, 1, 0, -1, 0]
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    for d in range(4):
                        nr, nc = r + directions[d], c + directions[d + 1]
                        if min(nr, nc) < 0 or nr == ROWS or nc == COLS:
                            dsu.union(N, index(r, c))
                        elif grid[nr][nc] == 0:
                            dsu.union(index(r, c), index(nr, nc))

        res = 0
        rootN = dsu.find(N)
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    continue
                node = index(r, c)
                root = dsu.find(node)
                if root == node and root != rootN:
                    res += 1
        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the given grid.

Common Pitfalls

Short-Circuit Evaluation in DFS

Using short-circuit evaluation (like return dfs(up) && dfs(down) && dfs(left) && dfs(right)) stops exploring the moment one direction returns false. This leaves parts of the island unvisited, causing them to be counted as separate islands later. Always explore ALL four directions before returning, even if you know the island is not closed.

Confusing Land and Water Values

Mixing up which value represents land (0) and which represents water (1) is a common source of bugs. In this problem, 0 is land and 1 is water, which is counterintuitive compared to many other grid problems. Double-check the problem statement and ensure your conditions correctly identify land cells.

Forgetting to Handle Boundary-Connected Islands

Counting islands that touch the grid boundary as closed islands is incorrect. Any island with at least one cell on the first row, last row, first column, or last column cannot be closed. Either pre-process boundary islands to mark them as water, or track during DFS/BFS whether the island touches the boundary.