#1254

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Number of Closed Islands

Count the number of closed islands in a 2D grid using array traversal and depth-first search efficiently.

array depth first search breadth first search union find matrix

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.

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.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            res = int(0 < i < m - 1 and 0 < j < n - 1)
            grid[i][j] = 1
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
                    res &= dfs(x, y)
            return res

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        return sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))

Solution 2: Union-Find

We can use a union-find set to maintain each piece of connected land.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            res = int(0 < i < m - 1 and 0 < j < n - 1)
            grid[i][j] = 1
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
                    res &= dfs(x, y)
            return res

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        return sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))

Continue Practicing

#1267 count servers that communicate #1391 check if there is a valid path in a grid #1020 number of enclaves