MediumNo. 1905
Count Sub Islands — LeetCode 1905 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Matrix
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical).
Example
- Input
- grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
- Output
- 3
- Explanation
- In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
Python solution
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
def dfs(i: int, j: int) -> int:
ok = grid1[i][j]
grid2[i][j] = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid2[x][y] and not dfs(x, y):
ok = 0
return ok
m, n = len(grid1), len(grid1[0])
dirs = (-1, 0, 1, 0, -1)
return sum(dfs(i, j) for i in range(m) for j in range(n) if grid2[i][j])Complexity
- Time
- O(m × n)
- Space · auxiliary
- O(m × n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1905. Count Sub Islands is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0695 | Max Area of Island | Medium |
| 0827 | Making A Large Island | Hard |
| 1020 | Number of Enclaves | Medium |
| 1254 | Number of Closed Islands | Medium |
Frequently asked questions
- How hard is LeetCode 1905. Count Sub Islands?
LeetCode 1905. Count Sub Islands is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1905. Count Sub Islands?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 1905. Count Sub Islands?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 1905. Count Sub Islands cover?
LeetCode 1905. Count Sub Islands is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.