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.

Description Hints 2 Solution Video 13:48

1254. Number of Closed Islands

Medium70.4% acceptance5 companies

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

Asked at 5 companies

Google Oracle Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Exclude connected group of 0s on the corners because they are not closed island.

Hint 2

Return number of connected component of 0s on the grid.

13:48

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def closedIsland(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[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]]

Input

[[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]

Input

[[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]]

Your code is saved on this device.Solution