Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
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: Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] Output: 1
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
Constraints:
1 <= grid.length, grid[0].length <= 1000 <= grid[i][j] <=1Problem Overview: You are given a 2D grid where 0 represents land and 1 represents water. A closed island is a group of land cells completely surrounded by water and not touching the grid boundary. The task is to count how many such islands exist.
Approach 1: Depth-First Search (DFS) with Edge Checking (Time: O(m*n), Space: O(m*n))
This approach treats the grid as a graph and performs a DFS traversal from every unvisited land cell. During the DFS, you recursively explore four directions (up, down, left, right) and mark cells as visited. If any part of the island touches the grid boundary, the island cannot be closed. The key idea is to propagate a boolean flag during recursion that tracks whether the exploration ever reaches the edge. After the traversal finishes, only islands that never touched the boundary are counted. DFS works well because it naturally explores connected components in a matrix using Depth-First Search. This approach is concise and commonly expected in interviews.
Approach 2: Breadth-First Search (BFS) with Queue (Time: O(m*n), Space: O(m*n))
The BFS solution follows the same connected-component idea but replaces recursion with an explicit queue. When you find an unvisited land cell, push it into a queue and perform level-order exploration across its neighbors. While processing cells, track whether any coordinate lies on the boundary. If the component touches the grid edge, mark the island as open; otherwise, increment the closed island count after the traversal completes. BFS avoids recursion depth issues and can be easier to reason about in large grids. This method uses Breadth-First Search for systematic exploration and is equally optimal in terms of complexity.
Recommended for interviews: DFS with edge checking is usually the fastest to implement and easier to explain during interviews. It demonstrates your understanding of connected components in grids and recursive traversal. BFS is equally correct and useful when recursion depth might be a concern. Interviewers mainly expect you to recognize the problem as a graph traversal on a grid and solve it using DFS or BFS flood fill.
The grid can be viewed as a graph where each cell is a node connected to its four possible neighbors. To identify closed islands, we can use a DFS approach starting from any cell containing 0 (cell of land). This DFS should mark the entire island by changing those 0s to a visited flag, such as -1. During the traversal, if any part of the island reaches the grid's boundary, it cannot be a closed island.
For each unvisited 0, if it forms a complete island (i.e., it does not reach the boundary), we increment the closed island count. We examine cells systematically, ensuring that all possible islands are accounted for.
The C solution uses a recursive DFS function called dfs. For each cell containing 0, it triggers a DFS which marks the visited islands with -1. The boolean flag isClosed helps determine if the island touches the boundary.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n) due to the recursion stack.
This approach employs BFS to traverse the islands. By leveraging a queue, we can iteratively explore all 0-connected land cells starting from each unvisited land cell. If during any BFS iteration, we find ourselves at the boundary or edge of the grid, the ongoing island is not closed.
Using BFS here can make iterative exploration more intuitive and can be preferred in languages where managing stacks explicitly is a common challenge, although the core logic of edge-checking remains similar.
The C solution employs a manual queue for BFS due to language constraints. The grid modifies in place, leveraging BFS to spread through each island starting from unvisited land cells.
Time Complexity: O(m * n), where m is the number of rows, and n is the number of columns.
Space Complexity: O(m + n) due to the queue memory usage during BFS.
We traverse the matrix, and for each piece of land, we perform a depth-first search to find all the land connected to it. Then we check if there is any land on the boundary. If there is, it is not a closed island; otherwise, it is a closed island, and we increment the answer by one.
Finally, we return the answer.
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.
We can use a union-find set to maintain each piece of connected land.
We traverse the matrix, if the current position is on the boundary, we connect it with the virtual node m times n. If the current position is land, we connect it with the land below and to the right.
Then, we traverse the matrix again, for each piece of land, if its root node is itself, we increment the answer by one.
Finally, we return the answer.
The time complexity is O(m times n times \alpha(m times n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the matrix, respectively.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) with Edge Checking | Time Complexity: O(m * n), where |
| Breadth-First Search (BFS) with Queue | Time Complexity: O(m * n), where |
| DFS | — |
| Union-Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) with Edge Checking | O(m*n) | O(m*n) | Best general solution. Simple recursion for exploring connected land cells. |
| Breadth-First Search (BFS) with Queue | O(m*n) | O(m*n) | Useful when avoiding recursion or handling very deep grids. |
Number of Closed Islands - Leetcode 1254 - Python • NeetCodeIO • 24,034 views views
Watch 9 more video solutions →Practice Number of Closed Islands with our built-in code editor and test cases.
Practice on FleetCode