Skip to main content
Talentd

Number of Closed Islands - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find32 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 <= 100
  • 0 <= grid[i][j] <=1

Approach Overview

Problem 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.

Approach 1: Depth-First Search (DFS) with Edge Checking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Breadth-First Search (BFS) with Queue

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: DFS

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Approach 4: Union-Find

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS) with Edge Checking

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.

Breadth-First Search (BFS) with Queue

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.

DFS—
Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (DFS) with Edge CheckingO(m*n)O(m*n)Best general solution. Simple recursion for exploring connected land cells.
Breadth-First Search (BFS) with QueueO(m*n)O(m*n)Useful when avoiding recursion or handling very deep grids.

Video Solution

Number of Closed Islands - Leetcode 1254 - Python • NeetCodeIO • 25,050 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Closed Islands easy or hard?
Number of Closed Islands is typically rated Medium difficulty. The challenge lies in recognizing that islands touching the grid boundary must be excluded and implementing a correct DFS or BFS traversal to track that condition.
Number of Closed Islands Python/Java solution
In Python or Java, implement DFS or BFS to explore four directions from each land cell. Mark visited cells by modifying the grid or using a separate visited array. If any explored cell lies on the boundary, the island is not closed. The final count includes only islands fully surrounded by water.
How to solve Number of Closed Islands in O(n)?
Treat the grid as a graph and perform DFS or BFS from every unvisited land cell. While exploring neighbors, check whether any part of the island touches the grid boundary. If the traversal never reaches the edge, increment the closed island count. Every cell is processed once, resulting in O(m*n) time complexity.
What is the best approach for Number of Closed Islands?
The most common approach is Depth-First Search (DFS) to explore each connected land component. During traversal, track whether any cell touches the grid boundary. If it does, the island is not closed. This DFS flood fill runs in O(m*n) time and O(m*n) space and is typically expected in coding interviews.
Is Number of Closed Islands asked at Google/Amazon/Meta?
Grid traversal and island-counting problems are common at companies like Amazon, Google, and Meta. Variants such as Number of Islands, Closed Islands, and Surrounded Regions frequently appear in interviews because they test DFS/BFS graph traversal on matrices.
What data structure is used in Number of Closed Islands?
The main data structures are the grid itself and either a recursion stack (for DFS) or a queue (for BFS). These structures help traverse connected components of land cells while marking visited positions to avoid repeated work.
What is the time complexity of Number of Closed Islands?
The optimal DFS or BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once during traversal. The space complexity is O(m*n) in the worst case due to recursion stack or queue storage for large land regions.

Ready to solve this problem?

Practice Number of Closed Islands with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays