NeetCode #613LC-305HardGraphsNC Algo100
← Back to All Problems#613 · #305 · Number of Islands II(岛屿数量 II)
📌 Problem Statement & Constraints
You are given
m, n and a list of positions where land is added one cell at a time. After each addition, return the number of islands. Constraints: 1 <= m, n <= 10^4, 1 <= positions.length <= 10^4, 1 <= m * n <= 10^4.💡 Core Algorithmic Approaches
- Adding land merges islands, so union-find is the natural incremental structure.
- When a cell is added, it starts as a new island (count + 1).
- For each of its four already-land neighbours, union them; each successful union decrements the count.
- Duplicate positions in the input must be ignored.
💻 Benchmark Python3 Implementation
class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
parent = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
count = 0
res = []
for r, c in positions:
if (r, c) in parent: # already land -> no change
res.append(count)
continue
parent[(r, c)] = (r, c) # new island
count += 1
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nb = (r + dr, c + dc)
if nb in parent:
ra, rb = find((r, c)), find(nb)
if ra != rb: # merge two islands
parent[ra] = rb
count -= 1
res.append(count)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(k * alpha(k)) where k is the number of positions.
💾 Space Complexity
O(k) for the union-find map.
⚠️ Interview Pitfalls & Follow-ups
- Recomputing the island count with a full BFS per query: O(k * m * n).
- Forgetting the duplicate-position case: the count must not change.
- Incrementing the count before the neighbour merges: the order does not matter, but the count must start at +1 for the new cell.
- Using a 2D parent array of size m*n: it works when
m*n <= 10^4, but a dict keyed by coordinate is more flexible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.