Number of Islands II
Hard · Graphs · Explanation and code example
Union Find
How it works
We need to track islands dynamically as land cells are added one at a time. Union-Find is ideal for this because it efficiently merges sets and counts distinct groups. Each time we add a land cell, we check its four neighbors. If a neighbor is already land, we union the new cell with that neighbor. The island count increases by 1 for each new land cell added, then decreases by 1 for each successful union with an adjacent island.
Steps
- Initialize a Union-Find structure with all cells marked as water (
parent = -1) and islandcount = 0. - For each position in the
positionsarray:- If this cell is already land, record the current
countand continue. - Mark the cell as land, set its parent to itself, and increment the island
count. - Check all four neighbors (up, down, left, right). For each neighbor that is land, union it with the new cell (this decrements the
countif they were in different sets). - Append the current island
countto the result.
- If this cell is already land, record the current
- Return the result array.
Complexity
- Time complexity:
O(m × n + l) - Space complexity:
O(m × n)
Where
mandnare the number of rows and columns in the given grid, andlis the size ofpositions.
Things to watch for
Forgetting to Handle Duplicate Positions
The input positions array may contain duplicate coordinates. If you add a land cell that already exists, you should not increment the island count again. Always check if a cell is already land before processing it as a new addition.
Incorrect 2D to 1D Index Conversion
When flattening a 2D grid to a 1D array for Union-Find, the conversion formula row * n + col must use the number of columns n, not the number of rows m. Mixing these up leads to incorrect neighbor calculations and wrong union operations.
Not Decrementing Count on Successful Union
When unioning two land cells that belong to different islands, the island count must decrease by 1. A common mistake is to always decrement, even when the cells are already in the same set. Only decrement when find(x) != find(y) before the union operation.
Bounds Checking Before Index Calculation
When checking neighbors, you must validate that neighborX and neighborY are within grid bounds before computing neighborPosition = neighborX * n + neighborY. Otherwise, negative indices or out-of-bounds positions can cause array access errors or incorrect unions with unrelated cells.
Missing Path Compression or Union by Rank
While the algorithm works without optimizations, omitting path compression in find() or union by rank can degrade performance from near-constant time to linear time per operation. For large inputs, this can cause Time Limit Exceeded errors.
Python code example
from typing import List
class UnionFind:
def __init__(self, size):
self.parent = [-1] * size
self.rank = [0] * size
self.count = 0
def add_land(self, x):
if self.parent[x] >= 0:
return
self.parent[x] = x
self.count += 1
def is_land(self, x):
if self.parent[x] >= 0:
return True
else:
return False
def number_of_islands(self):
return self.count
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):
xset = self.find(x)
yset = self.find(y)
if xset == yset:
return
elif self.rank[xset] < self.rank[yset]:
self.parent[xset] = yset
elif self.rank[xset] > self.rank[yset]:
self.parent[yset] = xset
else:
self.parent[yset] = xset
self.rank[xset] += 1
self.count -= 1
class Solution:
def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
x = [-1, 1, 0, 0]
y = [0, 0, -1, 1]
dsu = UnionFind(m * n)
answer = []
for position in positions:
land_position = position[0] * n + position[1]
dsu.add_land(land_position)
for i in range(4):
neighbor_x = position[0] + x[i]
neighbor_y = position[1] + y[i]
neighbor_position = neighbor_x * n + neighbor_y
# If neighborX and neighborY correspond to a point in the grid and there is a
# land at that point, then merge it with the current land.
if neighbor_x >= 0 and neighbor_x < m and neighbor_y >= 0 and neighbor_y < n and dsu.is_land(neighbor_position):
dsu.union(land_position, neighbor_position)
answer.append(dsu.number_of_islands())
return answer
C++ code example
class UnionFind {
private:
vector<int> parent, rank;
int count;
public:
UnionFind(int size) {
parent.resize(size, -1);
rank.resize(size, 0);
count = 0;
}
void addLand(int x) {
if (parent[x] >= 0) return;
parent[x] = x;
count++;
}
bool isLand(int x) {
if (parent[x] >= 0) {
return true;
} else {
return false;
}
}
int numberOfIslands() { return count; }
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union_set(int x, int y) {
int xset = find(x), yset = find(y);
if (xset == yset) {
return;
} else if (rank[xset] < rank[yset]) {
parent[xset] = yset;
} else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
} else {
parent[yset] = xset;
rank[xset]++;
}
count--;
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
int x[] = {-1, 1, 0, 0};
int y[] = {0, 0, -1, 1};
UnionFind dsu(m * n);
vector<int> answer;
for (auto& position : positions) {
int landPosition = position[0] * n + position[1];
dsu.addLand(landPosition);
for (int i = 0; i < 4; i++) {
int neighborX = position[0] + x[i];
int neighborY = position[1] + y[i];
int neighborPosition = neighborX * n + neighborY;
// If neighborX and neighborY correspond to a point in the grid and there is a land
// at that point, then merge it with the current land.
if (neighborX >= 0 && neighborX < m && neighborY >= 0 && neighborY < n &&
dsu.isLand(neighborPosition)) {
dsu.union_set(landPosition, neighborPosition);
}
}
answer.push_back(dsu.numberOfIslands());
}
return answer;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.