1254. Number of Closed Islands

2026, Oct 24 2 mins read

1. Description

In the binary matrix grid, 0 represents land and 1 represents water.
An island consists of a maximal group of land cells connected horizontally or vertically. It is closed when water surrounds it on all four sides, with no land cell in the group touching the grid boundary.
Count how many islands are closed.

2. Example

Example 1

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: The large land component in the interior and the single land cell at row 3, column 6 are surrounded by water. All other land components touch the boundary. Coordinates are zero-based.

Example 2

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Explanation: Only the land cell at row 1, column 2 forms a closed island. The other land components reach the boundary.

Example 3

Input: grid = [[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 ring of land and the isolated central land cell form two separate closed islands.

3. Constraints

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <= 1

4. Solutions

Breadth-First Search

m = grid.size(), n = grid.front().size()
Time complexity: O(mn)
Space complexity: O(mn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int closedIsland(vector<vector<int>> &grid) {
        const int m = grid.size(), n = grid.front().size();
        const array<array<int, 2>, 4> directions{{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};

        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    queue<pair<int, int>> nodes{{{i, j}}};
                    grid[i][j] = 2;

                    bool valid = true;
                    while (!nodes.empty()) {
                        auto [row, column] = nodes.front();
                        nodes.pop();

                        if (row == 0 || row == m - 1 || column == 0 || column == n - 1) {
                            valid = false;
                        }

                        for (const auto &[dr, dc] : directions) {
                            int next_row = row + dr;
                            int next_column = column + dc;

                            if (next_row < 0 || next_row >= m || next_column < 0 ||
                                next_column >= n) {
                                continue;
                            }

                            if (grid[next_row][next_column] == 0) {
                                grid[next_row][next_column] = 2;
                                nodes.push({next_row, next_column});
                            }
                        }
                    }

                    if (valid) {
                        ++count;
                    }
                }
            }
        }
        return count;
    }
};