How do you solve Count Sub Islands on LeetCode?

Count Sub Islands (LeetCode #1905) 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: Sub-islands must be completely contained within an island in grid1.

What is the brute force solution for Count Sub Islands?

The brute force approach for Count Sub Islands is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check each cell in grid2 to see if it starts a new island. For each island found, we will verify if all its cells are also part of an island in grid1. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Count Sub Islands?

Count Sub Islands uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search, Grid Traversal.

What are the interview tips for Count Sub Islands?

Explain your thought process clearly while coding. Consider edge cases, such as grids with no islands. Practice DFS and BFS traversal techniques.

What are common mistakes when solving Count Sub Islands?

Not marking cells as visited, leading to infinite loops. Failing to check all cells in grid1 corresponding to grid2.

#1905

Count Sub Islands

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First SearchGrid 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 by directly modifying grid2 during the DFS. If we find an island in grid2, we check if it is entirely contained within grid1, counting it if true.

⚙️

Algorithm

4 steps

1Step 1: Iterate through each cell in grid2.
2Step 2: When a '1' is found, perform a DFS to explore the entire island.
3Step 3: During DFS, check if each cell in grid2 corresponds to a '1' in grid1.
4Step 4: If all cells match, increment the sub-island count.

solution.py22 lines

1# Full working Python code
2
3def countSubIslands(grid1, grid2):
4    def dfs(x, y):
5        if x < 0 or x >= len(grid2) or y < 0 or y >= len(grid2[0]) or grid2[x][y] == 0:
6            return True
7        if grid1[x][y] == 0:
8            is_sub_island = False
9        grid2[x][y] = 0  # Mark as visited
10        up = dfs(x - 1, y)
11        down = dfs(x + 1, y)
12        left = dfs(x, y - 1)
13        right = dfs(x, y + 1)
14        return up and down and left and right and is_sub_island
15
16    count = 0
17    for i in range(len(grid2)):
18        for j in range(len(grid2[0])):
19            if grid2[i][j] == 1:
20                if dfs(i, j):
21                    count += 1
22    return count

ℹ

Complexity note: The time complexity remains O(n²) since we still need to potentially visit every cell in grid2, but we optimize space usage by modifying grid2 in place, leading to O(1) space complexity.

1Sub-islands must be completely contained within an island in grid1.
2DFS is effective for exploring connected components in a grid.

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