Number of Closed Islands — Boundary DFS + Interior Count

Problem Statement#

LeetCode 1254 — Number of Closed Islands (Medium)

Given an m x n binary grid where 0 represents land and 1 represents water, return the number of closed islands. A closed island is a group of 0s (land) completely surrounded by 1s (water) — none of the land cells touch the boundary of the grid.

Constraints:

• 1 <= m, n <= 100
• grid[i][j] is 0 or 1

Example 1:

Input:
1 1 1 1 1 1 1 0
1 0 0 0 0 1 1 0
1 0 1 0 1 1 1 1
1 0 0 0 0 1 0 0
1 1 1 1 1 1 1 0
 
Output: 2
Explanation: Two land components are fully enclosed by water.
             The cells touching the right border are NOT closed.

Example 2:

Input:
0 0 1 0 0
0 1 0 1 0
0 1 1 1 0
 
Output: 1
Explanation: Only the center land cell (1,1) is a closed island.
             All border-touching land is open.

Example 3:

Input:
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
 
Output: 2
Explanation: The outer ring of 0s forms one closed island;
             the single center 0 forms another closed island.

Why This Problem Matters#

This problem teaches a critical graph technique: eliminate the undesirable cases first, then count what remains. It is a direct application of boundary-based filtering — a pattern that appears repeatedly in grid problems:

• Surrounded Regions (LC 130) uses the same boundary-flood idea on Os
• Number of Enclaves (LC 1020) counts cells that cannot reach the border
• Pacific Atlantic Water Flow (LC 417) uses two-pass boundary BFS

The "flood from the border first" trick is something interviewers love because it tests whether you can think backwards: instead of asking "is this island closed?", you ask "is this island open?" and discard all open ones upfront. Inversion of the problem constraint is a transferable meta-skill.

The convention reversal (0 = land, 1 = water) is also intentional — it tests whether you read problem constraints carefully rather than assuming the standard island encoding.

The Core Insight#

Any island that touches the grid boundary cannot be closed — it is "open" to the outside. So the approach is:

1. Flood-fill all border-connected land (0s) → water (1s). This erases every open island. Any land cell reachable from the grid boundary is not closed.
2. Count the remaining connected 0-components in the interior. Each remaining component is a closed island because it was not reachable from any border cell.

This is a two-pass DFS: the first pass "masks out" all border-touching land, and the second pass counts the truly interior components.

The key observation is that connectivity to the border is transitive — if any cell in an island touches the border, the entire island is open and should be eliminated.

Visual Dry Run#

Original grid (0=land, 1=water):
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: Flood-fill from all 4 borders.
  All border cells are 1 (water) — nothing to flood.
  No interior 0s are reachable from the border.
 
After Step 1 (grid unchanged):
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 2: Count remaining 0-components.
  Start at (1,1): DFS visits (1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)
  All 8 cells form one connected component → count = 1
 
Answer: 1 closed island (the ring of land around the center water cell)

Another example showing border flood:

Original:
0 1 1
0 0 1
1 0 0
 
Step 1: Flood from borders.
  (0,0)=0 → on border → flood: (0,0)→1, (1,0)→1, (1,1)→1
  (2,1)=0 → on border → flood: (2,1)→1, (2,2)→1
 
After flood:
1 1 1
1 1 1
1 1 1
 
Step 2: No remaining 0s → 0 closed islands.

Common Mistakes#

1. Confusing 0 and 1 encoding. In this problem, 0 = land and 1 = water — the opposite of the standard Number of Islands problem. Applying the wrong convention leads to flood-filling water instead of land.

2. Counting border-touching islands. Forgetting to eliminate border-connected land before counting. If you just count all connected 0-components, you include the open islands that touch the border.

3. Only checking corner border cells. The border includes the entire first row, last row, first column, and last column — not just the four corners. Missing any border cell leaves some open islands un-eliminated.

4. Returning false from a DFS that merely touches the border instead of flood-filling. Some solutions try to return a boolean "is this island closed?" — this is correct but more complex. The flood-fill-then-count approach is simpler and less error-prone.

5. Using the grid as visited array but forgetting the second DFS pass also modifies it. After the first flood-fill pass, the grid is altered. The second counting pass's DFS must also mark visited cells to avoid double-counting; using the same "set to 1" approach works since 1 = water.

6. Off-by-one in boundary loops. When seeding the border flood-fill, the loops must cover r = 0 and r = R-1 across all columns, and c = 0 and c = C-1 across all rows. Missing any side leaves border islands intact.

Solutions#

Python#

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        R, C = len(grid), len(grid[0])   # grid dimensions
 
        def dfs(r, c):
            # stop if out of bounds or not land
            if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 0:
                return
            grid[r][c] = 1               # mark as water (visited)
            # explore all 4 neighbors
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                dfs(r + dr, c + dc)
 
        # Pass 1: flood-fill all border-connected land → eliminate open islands
        for r in range(R):
            dfs(r, 0)        # left border column
            dfs(r, C - 1)    # right border column
        for c in range(C):
            dfs(0, c)        # top border row
            dfs(R - 1, c)    # bottom border row
 
        # Pass 2: count remaining interior land components = closed islands
        count = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 0:      # found an unvisited interior land cell
                    dfs(r, c)            # flood-fill this closed island
                    count += 1           # increment island count
 
        return count

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var closedIsland = function(grid) {
    const R = grid.length;          // number of rows
    const C = grid[0].length;       // number of columns
 
    // DFS to flood-fill connected land cells with water (0 → 1)
    function dfs(r, c) {
        // base case: out of bounds or already water
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== 0) return;
        grid[r][c] = 1;             // mark land as water (visited)
        dfs(r + 1, c);              // down
        dfs(r - 1, c);              // up
        dfs(r, c + 1);              // right
        dfs(r, c - 1);              // left
    }
 
    // Pass 1: eliminate all border-touching land (open islands)
    for (let r = 0; r < R; r++) {
        dfs(r, 0);                  // left column
        dfs(r, C - 1);              // right column
    }
    for (let c = 0; c < C; c++) {
        dfs(0, c);                  // top row
        dfs(R - 1, c);              // bottom row
    }
 
    // Pass 2: count remaining land components (all are closed islands)
    let count = 0;
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === 0) { // found interior unvisited land
                dfs(r, c);          // flood-fill to mark entire island
                count++;            // one more closed island found
            }
        }
    }
 
    return count;
};

Complexity Analysis#

• Time: Every cell is visited at most twice — once during border flood-fill (Pass 1) and once during the counting pass (Pass 2). Each DFS call does O(1) work, giving O(m * n) total.
• Space: The recursion stack can grow up to O(m * n) in the worst case (one giant island). The grid is modified in-place so no additional data structures are needed.

Follow-up Questions#

1. Without mutating the grid: Use a separate visited boolean matrix. The logic remains the same but you check visited[r][c] instead of grid[r][c] == 0 after marking.

2. Count closed island cells instead of islands: Sum the size of each interior component during Pass 2's DFS rather than incrementing a counter.

3. Iterative DFS with an explicit stack: Replace the recursive DFS with a stack-based loop to avoid Python's recursion limit on large grids.

4. What if we also want to count "open" islands? Run a separate count over all 0-components before Pass 1 (total islands) and subtract the closed count.

5. LC 1020 — Number of Enclaves: Nearly identical — count land cells that cannot reach the border, which is the cell-level version of this island-level problem.

This Pattern Solves#

• LC 130 — Surrounded Regions: Same boundary-flood trick on O characters
• LC 1020 — Number of Enclaves: Count cells not reachable from border
• LC 417 — Pacific Atlantic Water Flow: Two-boundary BFS, same mental model
• LC 694 — Number of Distinct Islands: Interior island analysis after boundary processing

Key Takeaways#

• Flood-fill from all four border edges first to eliminate all boundary-connected 0-islands
• After boundary elimination, each remaining connected component of 0s that is surrounded by 1s is a closed island
• Count remaining 0-islands with a standard DFS/BFS flood-fill on the cleaned grid
• Time O(mn), space O(mn) — each cell visited at most twice (once in boundary pass, once in counting pass)
• This boundary-elimination + count pattern directly solves LC 1020 (Number of Enclaves) and LC 130 (Surrounded Regions)
• In this problem, 0 represents land (islands) and 1 represents water — the opposite of LC 200, so read carefully
• The two-pass approach (eliminate border islands, then count) is cleaner than a single-pass with constraint checking