How do you solve Number of Closed Islands on LeetCode?

Number of Closed Islands (LeetCode #1254) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Closed islands cannot touch the boundary of the grid.

What is the brute force solution for Number of Closed Islands?

The brute force approach for Number of Closed Islands is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check each cell in the grid to see if it is part of a closed island by performing a DFS (Depth-First Search) from each unvisited land cell (0). If we reach the boundary of the grid during our search, we know it's not a closed island. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Number of Closed Islands?

Number of Closed Islands uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search (DFS), Grid Traversal.

What are the interview tips for Number of Closed Islands?

Always clarify the definition of closed islands with the interviewer. Consider edge cases, such as grids filled entirely with water or land. Explain your thought process clearly as you write code.

What are common mistakes when solving Number of Closed Islands?

Not marking boundary-connected land cells, leading to incorrect counts. Confusing closed islands with open islands.

#1254

Number of Closed Islands

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First Search (DFS)Grid Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

We can optimize our approach by using a similar DFS method but first marking all the land cells (0s) connected to the grid's boundary as visited. This way, we only need to check the inner cells for closed islands, reducing unnecessary checks.

⚙️

Algorithm

3 steps

1Step 1: First, iterate through the boundary of the grid and perform DFS to mark all land cells connected to the boundary as visited.
2Step 2: Iterate through the inner cells of the grid. For each unvisited land cell (0), perform DFS to explore the island.
3Step 3: If the DFS completes without hitting the boundary, count it as a closed island.

solution.py25 lines

1def closedIsland(grid):
2    def dfs(x, y):
3        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
4            return
5        if grid[x][y] == 1:
6            return
7        grid[x][y] = 1  # mark as visited
8        dfs(x - 1, y)
9        dfs(x + 1, y)
10        dfs(x, y - 1)
11        dfs(x, y + 1)
12
13    # Mark boundary-connected land
14    for i in range(len(grid)):
15        for j in range(len(grid[0])):
16            if (i == 0 or i == len(grid) - 1 or j == 0 or j == len(grid[0]) - 1) and grid[i][j] == 0:
17                dfs(i, j)
18
19    count = 0
20    for i in range(1, len(grid) - 1):
21        for j in range(1, len(grid[0]) - 1):
22            if grid[i][j] == 0:
23                dfs(i, j)
24                count += 1
25    return count

ℹ

Complexity note: The time complexity remains O(n²) since we still potentially visit every cell in the grid. The space complexity is O(1) as we are using the grid itself for marking visited cells.

1Closed islands cannot touch the boundary of the grid.
2Marking boundary-connected land cells first helps reduce unnecessary checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.