Number of Islands II
Asked at Uber
Problem
You are given an empty 2D grid and a list of positions to be added one at a time. Each position turns a water cell into a land cell. After each addition, return the number of distinct islands in the grid. Two cells are part of the same island if they are adjacent horizontally or vertically.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | HARD | View all Uber questions → |
How to Think About It
Brute force: after each addition, run BFS/DFS on the entire grid to count islands — O(m * n * k) time.
Use Union-Find to maintain connected components as cells are added incrementally.
When adding a cell, initialize it as its own component and union it with any adjacent land cells.
Track the number of components: start at 0, add 1 for each new cell, subtract 1 for each successful union.
Optimal: Union-Find with path compression and union by rank gives near O(1) per operation amortized.
Optimal Approach
Use a Union-Find data structure. For each added land cell, create a new component and check its four neighbors. If a neighbor is land, union the two cells and decrement the component count. After processing each addition, record the current number of distinct islands. Union-Find with path compression and union by rank ensures each operation is amortized O(α(mn)) ≈ O(1), giving overall O(k * α(mn)) time.
What Trips People Up in Real Interviews
Clarify whether the grid dimensions are fixed or dynamic — they are fixed here.
Map 2D coordinates to 1D IDs using id = row * nCols + col for the Union-Find array.
Remember that adding a water cell (already land) does not change the island count.
Ask if diagonal adjacency counts — it does not, only horizontal and vertical.
Explain path compression and union by rank to justify the amortized time complexity.
Solution Code
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True
def numIslands2(self, m, n, positions):
uf = UnionFind(m * n)
grid = [[0] * n for _ in range(m)]
result = []
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for r, c in positions:
if grid[r][c] == 1:
result.append(uf.count)
continue
grid[r][c] = 1
uf.count += 1
idx = r * n + c
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
uf.union(idx, nr * n + nc)
result.append(uf.count)
return resultFrequently Asked Questions
What is the Number of Islands II problem?
You are given an empty 2D grid and a list of positions to be added one at a time. Each position turns a water cell into a land cell. After each addition, return the number of distinct islands in the grid. Two cells are part of the same island if they are adjacent horizontally or vertically.
How do you solve Number of Islands II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Islands II?
Number of Islands II is asked at Uber. It is a hard difficulty problem.
What are common mistakes on Number of Islands II?
- Clarify whether the grid dimensions are fixed or dynamic — they are fixed here.
- Map 2D coordinates to 1D IDs using id = row * nCols + col for the Union-Find array.
- Remember that adding a water cell (already land) does not change the island count.
- Ask if diagonal adjacency counts — it does not, only horizontal and vertical.
- Explain path compression and union by rank to justify the amortized time complexity.