305. Number of Islands II
Asked at Uber
Difficulty
Hard
Time
O(k * α(m*n))
Space
O(m*n)
Pattern
Array
Companies
1
Problem
You start with an m x n grid that is all water. You are given a list of positions. Each position [r, c] is an operation that turns that water cell into land.
After each operation, you must report how many islands exist. An island is a group of land cells connected horizontally or vertically (not diagonally). Water separates islands.
Return an array answer where answer[i] is the number of islands right after the i-th operation. If a position is already land, the grid does not change, but you still record the current island count.
Adding land one cell at a time
Constraints
- ●
1 <= m, n, positions.length <= 10^4 - ●
1 <= m * n <= 10^4 - ●
positions[i].length == 2 - ●
0 <= ri < m - ●
0 <= ci < n
Examples
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]][1,1,2,3]m = 1, n = 1, positions = [[0,0]][1]Asked At
1 companies| 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.
Union-Find tracks island count
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
O(k * α(m*n)) timeclass 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 runs in O(k * α(m*n)) time and O(m*n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.