The Number of Islands II problem on Leetcode asks you to dynamically track the number of islands in a 2D grid as land is added. You are given the grid's dimensions, m rows and n columns, and a list of positions where each position is a coordinate (row, col) where land is added (from water). Initially, the grid is all water (represented by 0). Each time you add land (1), you must report the current number of islands.
1s (land) connected vertically or horizontally.Constraints:
The naive approach would be to rebuild the entire grid and recount islands after each addition, using DFS or BFS for connected components. However, this is inefficient as the grid can be very large and there can be many additions.
We need a way to efficiently merge and track connected components as new land is added. The Union-Find (Disjoint Set Union) data structure is ideal for this, as it can quickly join sets (merge islands) and check if two lands are in the same island.
The key insight is: each new land can either create a new island or connect to existing neighboring islands, possibly merging them into one. So, we should:
We'll use a Union-Find (Disjoint Set Union) structure with path compression for efficiency. Here's the step-by-step approach:
positions:
(row, col) to a unique id: row * n + col.Why Union-Find? Union-Find allows us to efficiently merge and query connected components (islands) in nearly constant time, making it suitable for dynamic connectivity problems like this.
Let's walk through an example with m = 3, n = 3, and positions = [[0,0],[0,1],[1,2],[2,1],[1,1]].
The result is [1,1,2,3,1].
Brute-force Approach:
The Number of Islands II problem is efficiently solved by dynamically tracking connected components using the Union-Find data structure. By representing each land cell as a node and merging connected neighbors, we can quickly update and report the number of islands after each land addition. This approach is highly efficient and scales well even for large grids, thanks to the nearly constant-time operations of Union-Find with path compression.
class Solution:
def numIslands2(self, m, n, positions):
parent = {}
res = []
count = 0
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootx = find(x)
rooty = find(y)
if rootx != rooty:
parent[rootx] = rooty
return True
return False
directions = [(0,1),(1,0),(-1,0),(0,-1)]
for r, c in positions:
idx = r * n + c
if idx in parent:
res.append(count)
continue
parent[idx] = idx
count += 1
for dr, dc in directions:
nr, nc = r + dr, c + dc
nidx = nr * n + nc
if 0 <= nr < m and 0 <= nc < n and nidx in parent:
if union(idx, nidx):
count -= 1
res.append(count)
return res
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<int> res;
unordered_map<int, int> parent;
int count = 0;
vector<pair<int, int>> dirs{{0,1},{1,0},{-1,0},{0,-1}};
function<int(int)> find = [&](int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
};
auto union_set = [&](int x, int y) {
int rx = find(x);
int ry = find(y);
if (rx != ry) {
parent[rx] = ry;
return true;
}
return false;
};
for (auto& pos : positions) {
int r = pos[0], c = pos[1];
int idx = r * n + c;
if (parent.count(idx)) {
res.push_back(count);
continue;
}
parent[idx] = idx;
count++;
for (auto& d : dirs) {
int nr = r + d.first, nc = c + d.second;
int nidx = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && parent.count(nidx)) {
if (union_set(idx, nidx))
count--;
}
}
res.push_back(count);
}
return res;
}
};
class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
Map<Integer, Integer> parent = new HashMap<>();
int count = 0;
int[][] dirs = {{0,1},{1,0},{-1,0},{0,-1}};
Function<Integer, Integer> find = new Function<Integer, Integer>() {
public Integer apply(Integer x) {
if (!parent.get(x).equals(x))
parent.put(x, this.apply(parent.get(x)));
return parent.get(x);
}
};
for (int[] pos : positions) {
int r = pos[0], c = pos[1];
int idx = r * n + c;
if (parent.containsKey(idx)) {
res.add(count);
continue;
}
parent.put(idx, idx);
count++;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
int nidx = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && parent.containsKey(nidx)) {
int rootIdx = find.apply(idx);
int rootNidx = find.apply(nidx);
if (rootIdx != rootNidx) {
parent.put(rootIdx, rootNidx);
count--;
}
}
}
res.add(count);
}
return res;
}
}
var numIslands2 = function(m, n, positions) {
const parent = {};
const res = [];
let count = 0;
const dirs = [[0,1],[1,0],[-1,0],[0,-1]];
function find(x) {
if (parent[x] !== x)
parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
let rootx = find(x), rooty = find(y);
if (rootx !== rooty) {
parent[rootx] = rooty;
return true;
}
return false;
}
for (const [r, c] of positions) {
const idx = r * n + c;
if (parent.hasOwnProperty(idx)) {
res.push(count);
continue;
}
parent[idx] = idx;
count++;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
const nidx = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && parent.hasOwnProperty(nidx)) {
if (union(idx, nidx)) count--;
}
}
res.push(count);
}
return res;
};