Start by marking all land connected to the grid edges as non-closed. Then, traverse the remaining grid using depth-first search to identify each fully enclosed island. Increment a counter for each island that does not touch the border, ensuring the solution handles arrays of varying size efficiently.
Problem Statement
You are given a 2D grid consisting of 0s (land) and 1s (water). An island is defined as a group of 0s connected 4-directionally. A closed island is an island completely surrounded by 1s on all sides including edges. Your task is to determine the total number of closed islands present in the grid.
Write a function that receives the grid and returns the number of closed islands. Be careful to exclude islands connected to the borders since they cannot be closed. For example, given 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]], the correct output is 2 because only two islands are fully enclosed by water.
Examples
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
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 details omitted.
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
Example details omitted.
Constraints
- 1 <= grid.length, grid[0].length <= 100
- 0 <= grid[i][j] <=1
Solution Approach
Edge Elimination
Traverse the borders of the grid and apply depth-first search to mark all land cells (0s) connected to the edges. This ensures that only potential closed islands remain for counting.
Depth-First Search Counting
Iterate through the internal cells of the grid. When an unvisited land cell is found, perform DFS to mark all connected land cells. Increment a counter only if the island does not touch any previously marked border land.
Alternative BFS Approach
Instead of DFS, you can use breadth-first search to traverse each island. BFS offers the same correctness for counting closed islands but may affect stack depth issues on large grids compared to DFS.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(m \cdot n) |
| Space | O(m \cdot n) |
Time complexity is O(m \cdot n) since every cell is visited at most twice (once during edge marking and once during island counting). Space complexity is O(m \cdot n) due to recursion stack or queue for DFS/BFS traversal of connected land cells.
What Interviewers Usually Probe
- Check if candidate correctly excludes border-connected land before counting islands.
- Watch for correct 4-directional connectivity handling in DFS or BFS.
- Confirm handling of varying grid sizes up to 100x100 without stack overflow.
Common Pitfalls or Variants
Common pitfalls
- Counting islands that touch the grid edge as closed islands.
- Using recursive DFS without considering maximum stack depth for large grids.
- Failing to mark visited cells, leading to double counting of islands.
Follow-up variants
- Return the size of the largest closed island instead of just the count.
- Allow diagonal connections when defining islands and adjust DFS/BFS accordingly.
- Use Union Find to dynamically merge land cells and detect closed islands.
How GhostInterview Helps
- Automatically highlights edge-connected land cells to prevent counting non-closed islands.
- Provides step-by-step DFS or BFS traversal hints to identify each closed island efficiently.
- Warns about common pitfalls like double counting or stack overflow, guiding array-based solutions.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is a closed island in this problem?
A closed island is a group of 0s connected 4-directionally that is completely surrounded by 1s and does not touch the grid edges.
Should I use DFS or BFS for counting closed islands?
Either DFS or BFS works; DFS is simpler for recursive marking, while BFS uses a queue to avoid deep recursion issues.
How do I handle islands touching the grid border?
Perform an initial traversal of all border cells to mark any connected land as non-closed before counting islands internally.
What is the time complexity for this solution?
The solution runs in O(m \cdot n) time because every cell is visited at most twice, once for edge marking and once for counting.
Can this problem be solved using Union Find?
Yes, Union Find can merge connected land cells and track whether a component touches the border to identify closed islands efficiently.
Need direct help with Number of Closed Islands instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Closed Islands from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count Servers that Communicate involves identifying servers in a grid that can communicate based on row or column connection.
Open problem page#1391 Check if There is a Valid Path in a GridCheck if there is a valid path from the upper-left to the bottom-right corner of a grid using depth-first search.
Open problem page#1020 Number of EnclavesThis problem involves finding the number of land cells that cannot reach the boundary in a grid using DFS and array manipulation.
Open problem page