1254. Number of Closed Islands

Array
Depth-First Search
Breadth-First Search
Matrix

TIME

O(m * n)

SPACE

O(m * n)

Intuition

An island is closed exactly when none of its cells is on the grid border. A cell on the border has open space beyond the grid on at least one side, so its island cannot be surrounded. An island with no border cell is, by maximality, bounded on every side by water: any land neighbour would belong to the island.

So each island needs one flood fill and one yes/no fact: did it touch the edge?

Approach

Scan every cell. On an unvisited 0, start a flood fill of its island with an explicit stack, marking cells visited by setting them to 1.
While flooding, set closed = False if any cell has r == 0, c == 0, r == m - 1 or c == n - 1.
When the stack empties, count the island if closed is still true.

The fill has to run to completion even after a border cell is found. Stopping early would leave the rest of the island unmarked, and the scan would later pick up the leftover piece and count it as a separate island, which may wrongly look closed.

The stack is explicit because a single winding island in a 100 x 100 grid can hold around 5000 cells, deeper than Python's default recursion limit.

Complexity

Time: O(m * n), every cell is pushed at most once
Space: O(m * n) in the worst case for the stack; the grid doubles as the visited set

Edge Cases

Grids with one row or one column → every cell is on the border, answer 0
All water → 0
All land → one island, touching the border, so 0
A ring of land around a lake around another island (example 3) → the inner island and the ring are both closed, giving 2
An island that touches the border at a single cell is open, and that cell can be far from where the flood started
Diagonal contact does not connect islands; only the four orthogonal neighbours are followed
The input grid is modified in place. That is fine for LeetCode; a caller that needs the grid afterwards should pass a copy

Code

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        """
        1254. Number of Closed Islands
        Time: O(m * n)
        Space: O(m * n)
        """
        m, n = len(grid), len(grid[0])
        count = 0

        for sr in range(m):
            for sc in range(n):
                if grid[sr][sc] != 0:
                    continue

                # flood the whole island even after it touches the border,
                # otherwise its leftover cells get counted as a new island
                closed = True
                grid[sr][sc] = 1
                stack = [(sr, sc)]
                while stack:
                    r, c = stack.pop()
                    if r == 0 or c == 0 or r == m - 1 or c == n - 1:
                        closed = False
                    for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
                            grid[nr][nc] = 1
                            stack.append((nr, nc))

                if closed:
                    count += 1

        return count

/**
 * 1254. Number of Closed Islands
 * Time: O(m * n)
 * Space: O(m * n)
 */
class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] stack = new int[m * n];  // cells encoded as r * n + c
        int count = 0;

        for (int sr = 0; sr < m; sr++) {
            for (int sc = 0; sc < n; sc++) {
                if (grid[sr][sc] != 0) {
                    continue;
                }

                // flood the whole island even after it touches the border,
                // otherwise its leftover cells get counted as a new island
                boolean closed = true;
                int top = 0;
                grid[sr][sc] = 1;
                stack[top++] = sr * n + sc;
                while (top > 0) {
                    int cell = stack[--top];
                    int r = cell / n, c = cell % n;
                    if (r == 0 || c == 0 || r == m - 1 || c == n - 1) {
                        closed = false;
                    }
                    for (int[] d : DIRS) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                            grid[nr][nc] = 1;
                            stack[top++] = nr * n + nc;
                        }
                    }
                }

                if (closed) {
                    count++;
                }
            }
        }

        return count;
    }
}