Number of Closed Islands

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

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.

Steps

  1. Create a DSU with size ROWS * COLS + 1, where index N = ROWS * COLS represents the boundary.
  2. 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.
  3. Find the root of the boundary node.
  4. 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.
  5. Return the count of distinct closed island components.

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.

Things to watch for

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.

Python code example

from typing import List

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

C++ code example

class DSU {
public:
    vector<int> Parent, Size;

    DSU(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
        }
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionSets(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }
};

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int ROWS = grid.size(), COLS = grid[0].size();
        int N = ROWS * COLS;

        DSU dsu(N);
        int directions[5] = {0, 1, 0, -1, 0};

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 0) {
                    for (int d = 0; d < 4; d++) {
                        int nr = r + directions[d], nc = c + directions[d + 1];
                        if (nr < 0 || nc < 0 || nr == ROWS || nc == COLS) {
                            dsu.unionSets(N, r * COLS + c);
                        } else if (grid[nr][nc] == 0) {
                            dsu.unionSets(r * COLS + c, nr * COLS + nc);
                        }
                    }
                }
            }
        }

        int res = 0, rootN = dsu.find(N);
        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 0) {
                    int node = r * COLS + c;
                    int root = dsu.find(node);
                    if (root == node && root != rootN) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations