python
# Pseudo-code for Naive Approach
count = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 0:
            if is_closed(r, c, visited_for_this_check):
                count += 1

The is_closed function would perform a traversal (like BFS or DFS). However, a naive implementation often fails to persist "visited" states globally. It might re-traverse the same land cells multiple times for different starting points, or fail to correctly propagate the "open" status (touching the boundary) back to the starting cell if the traversal logic is flawed.

Why it fails: While a correct brute force is essentially the optimal solution, inefficient implementations often lead to Time Limit Exceeded (TLE). If we do not mark cells as visited globally, the time complexity can degrade to $O((M \times N)^2)$ because we repeatedly traverse the same components. Furthermore, checking rows and columns independently without a proper graph traversal fails to account for complex, snake-like island shapes.

Core Insight for Number of Closed Islands

The core insight connecting the naive approach to the optimal pattern is the definition of "closed." An island is closed if and only if none of its constituent cells lie on the boundary of the grid.

If a Depth-First Search (DFS) traversal starts at a land cell and reaches the edge of the grid, the entire connected component is invalid (not closed). If the traversal completes visiting all connected land cells and never hits the grid boundary, the island is valid.

Pattern Invariant: We must ensure that we visit every node in a connected component to mark it as processed, even if we discover early on that the island is not closed. If we stop traversing immediately upon finding a boundary cell, we leave the rest of the component as 0s. The main loop would then encounter these unvisited parts later and incorrectly identify them as new, potentially valid islands.

Visual Description: Imagine the recursion tree expanding from a starting cell $(r, c)$. As the DFS flows into neighbor cells $(r+1, c), (r-1, c)$, etc., it effectively "floods" the island. If any branch of this recursion tree touches the grid coordinates $0$, $rows-1$, $0$, or $cols-1$, a "false" flag propagates back up the tree. The algorithm effectively asks every branch: "Did you hit a wall (boundary)?" If all branches reply "No, I only hit water," the island is closed.

Execution Flow

1. Initialize a counter closed_islands = 0.
2. Start loops: r from 0 to rows-1, c from 0 to cols-1.
3. Check condition: If grid[r][c] == 0:
   • Call dfs(grid, r, c).
   • If dfs returns true, increment closed_islands.
4. Inside dfs(grid, r, c):
   • Base Case 1 (Water): If grid[r][c] == 1, return true. This side is sealed by water.
   • Base Case 2 (Boundary Check): If r or c are out of bounds (or on the boundary, depending on implementation style), this implies the island is touching the edge. Return false.
   • Process Node: Mark grid[r][c] = 1 to mark as visited.
   • Recursive Step: Call dfs for up, down, left, right.
   • Logic Gate: Store the results of all 4 recursive calls.
     • isClosed = dfs(up) & dfs(down) & dfs(left) & dfs(right)
     • Note: We must execute ALL four calls to ensure the entire island is marked visited. We cannot use short-circuit operators (like && in C++ or and in Python) immediately, or we might leave parts of the island unvisited.
   • Return isClosed.
5. Return final closed_islands count.

Proof of Correctness

The algorithm is correct because the DFS traversal identifies Connected Components. By definition, a connected component is a maximal set of connected nodes.

1. Coverage: The loops ensure every land cell is checked.
2. Exclusivity: Marking visited cells (0 $\to$ 1) ensures each component is processed exactly once.
3. Validity: The boolean logic within the DFS enforces the "closed" constraint. The return value is true if and only if every path from the starting node terminates at a 1 (water) without crossing the grid boundary. If any path hits the boundary, the false value propagates to the root of the call, preventing the increment of the counter.

Reference Implementation

C++ Solution for LeetCode 1254

cpp
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // If dfs returns true, it's a closed island
                    if (dfs(grid, i, j, rows, cols)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

private:
    bool dfs(vector<vector<int>>& grid, int r, int c, int rows, int cols) {
        // Check bounds: if we go out of bounds, it means the island touches the edge
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }
        
        // If we hit water (1), this path is closed
        if (grid[r][c] == 1) {
            return true;
        }
        
        // Mark as visited
        grid[r][c] = 1;
        
        // Visit all 4 directions. 
        // IMPORTANT: We must visit ALL directions to mark the whole island.
        // Do not use short-circuiting && immediately.
        bool up = dfs(grid, r - 1, c, rows, cols);
        bool down = dfs(grid, r + 1, c, rows, cols);
        bool left = dfs(grid, r, c - 1, rows, cols);
        bool right = dfs(grid, r, c + 1, rows, cols);
        
        return up && down && left && right;
    }
};

Java Solution for LeetCode 1254

java
class Solution {
    public int closedIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    if (dfs(grid, i, j, rows, cols)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private boolean dfs(int[][] grid, int r, int c, int rows, int cols) {
        // If out of bounds, the island touches the edge -> not closed
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }

        // If water (1), this direction is sealed
        if (grid[r][c] == 1) {
            return true;
        }

        // Mark current land as visited (turn to water)
        grid[r][c] = 1;

        // Traverse all directions
        // We use variables to ensure all recursive calls execute
        boolean up = dfs(grid, r - 1, c, rows, cols);
        boolean down = dfs(grid, r + 1, c, rows, cols);
        boolean left = dfs(grid, r, c - 1, rows, cols);
        boolean right = dfs(grid, r, c + 1, rows, cols);

        return up && down && left && right;
    }
}

Python Solution for LeetCode 1254

python
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        def dfs(r, c):
            # If out of bounds, we hit the boundary -> not closed
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return False
            
            # If water, this path is valid (sealed)
            if grid[r][c] == 1:
                return True
            
            # Mark visited
            grid[r][c] = 1
            
            # IMPORTANT: Compute all directions individually.
            # Using `return dfs(...) and dfs(...)` directly would short-circuit,
            # potentially leaving parts of the island unvisited.
            up = dfs(r - 1, c)
            down = dfs(r + 1, c)
            left = dfs(r, c - 1)
            right = dfs(r, c + 1)
            
            return up and down and left and right

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    if dfs(r, c):
                        count += 1
                        
        return count