HardNo. 0305LeetCode Premium
Number of Islands II — LeetCode 305 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Array, Hash Table
- Reading time
- 8 min
- Source
- leetcode.com
The problem
You are given an empty 2D binary grid grid of size m x n. The grid represents a map where 0's represent water and 1's represent land.
Example
- Input
- m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
- Output
- [1,1,2,3]
- Explanation
- Initially, the 2d grid is filled with water.
Python solution
class UnionFind:
def __init__(self, n: int):
self.p = list(range(n))
self.size = [1] * n
def find(self, x: int):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a: int, b: int) -> bool:
pa, pb = self.find(a - 1), self.find(b - 1)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
uf = UnionFind(m * n)
grid = [[0] * n for _ in range(m)]
ans = []
dirs = (-1, 0, 1, 0, -1)
cnt = 0
for i, j in positions:
if grid[i][j]:
ans.append(cnt)
continue
grid[i][j] = 1
cnt += 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]
and uf.union(i * n + j, x * n + y)
):
cnt -= 1
ans.append(cnt)
return ansComplexity
- Time
- O(k × α(m × n)) or O(k × log(m × n)), where k is the length of positions, and α is the inverse function of the Ackermann function
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 305. Number of Islands II 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 |
|---|---|---|
| 0200 | Number of Islands | Medium |
| 0128 | Longest Consecutive Sequence | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
Frequently asked questions
- How hard is LeetCode 305. Number of Islands II?
LeetCode 305. Number of Islands II is rated Hard on LeetCode.
- What topics does LeetCode 305. Number of Islands II cover?
LeetCode 305. Number of Islands II is tagged Union Find, Array and Hash Table on LeetCode.
- Is LeetCode 305. Number of Islands II a premium problem?
Yes. LeetCode 305. Number of Islands II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.