Number of Islands I and II
XXX. Number of Islands
Depth-First Search
Union-Find
Problem Statement:
Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Additionally, in a dynamic version of the problem, you are given a grid of water and a sequence of positions where land is added. Return the number of islands after each addition.
Algorithm:
Part 1: Static Islands Count
- Iterate through the grid. For every
'1'(land): - Increment the island count.
- Perform a DFS to mark all connected
'1's as visited (change them to'0').
Part 2: Dynamic Islands Count
- Use a union-find structure to manage connected components.
- Initialize all grid cells as water (
-1in the union-find array). - For each land addition:
- Set the corresponding cell as its own parent and increment the island count.
- Check all four directions for adjacent land and union them if found, reducing the island count for each union operation.
Complexity:
Static Islands Count:
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n) for the recursive DFS stack.
Dynamic Islands Count:
Time Complexity: O(k * log(m * n)), where k is the number of positions and union-find operations are nearly constant due to path compression.
Space Complexity: O(m * n) for the union-find structure.
Java Implementation:
public int numIslands(char[][] grid) {
int count = 0;
// Iterate through the grid
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
if (grid[i][j] == '1') { // Found an unvisited land
destroyIsland(grid, i, j); // Mark all connected land
count++;
}
return count;
}
// Helper function to mark connected land using DFS
public void destroyIsland(char[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == '0')
return;
grid[x][y] = '0'; // Mark as visited
destroyIsland(grid, x + 1, y);
destroyIsland(grid, x, y + 1);
destroyIsland(grid, x - 1, y);
destroyIsland(grid, x, y - 1);
}
public List numIslands2(int m, int n, int[][] positions) {
int[] parent = new int[m * n];
List res = new ArrayList<>();
Arrays.fill(parent, -1); // Initialize as water
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int count = 0;
for (int[] pos : positions) {
int id = pos(pos[0], pos[1], n);
parent[id] = id; // Mark as land
count++;
for (int i = 0; i < dx.length; i++) {
int newX = pos[0] + dx[i];
int newY = pos[1] + dy[i];
int id2 = pos(newX, newY, n);
if (newX >= 0 && newY >= 0 && newX < m && newY < n && parent[id2] != -1) {
int x = find(id, parent);
int y = find(id2, parent);
if (x != y) {
union(x, y, parent);
count--;
}
}
}
res.add(count);
}
return res;
}
private int pos(int i, int j, int n) {
return i * n + j;
}
private int find(int i, int[] parent) {
if (parent[i] == i) return i;
parent[i] = find(parent[i], parent); // Path compression
return parent[i];
}
private void union(int x, int y, int[] parent) {
parent[find(y, parent)] = find(x, parent);
}
Python Implementation:
def numIslands(grid):
def destroyIsland(grid, x, y):
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':
return
grid[x][y] = '0'
destroyIsland(grid, x + 1, y)
destroyIsland(grid, x, y + 1)
destroyIsland(grid, x - 1, y)
destroyIsland(grid, x, y - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
destroyIsland(grid, i, j)
count += 1
return count
def numIslands2(m, n, positions):
def find(i):
if parent[i] != i:
parent[i] = find(parent[i])
return parent[i]
def union(x, y):
parent[find(y)] = find(x)
parent = [-1] * (m * n)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
count = 0
res = []
for x, y in positions:
id = x * n + y
if parent[id] == -1:
parent[id] = id
count += 1
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
nid = nx * n + ny
if 0 <= nx < m and 0 <= ny < n and parent[nid] != -1:
root1, root2 = find(id), find(nid)
if root1 != root2:
union(root1, root2)
count -= 1
res.append(count)
return res
C++ Implementation:
#include
#include
#include
using namespace std;
void destroyIsland(vector>& grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == '0')
return;
grid[x][y] = '0';
destroyIsland(grid, x + 1, y);
destroyIsland(grid, x, y + 1);
destroyIsland(grid, x - 1, y);
destroyIsland(grid, x, y - 1);
}
int numIslands(vector>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1') {
destroyIsland(grid, i, j);
count++;
}
}
}
return count;
}
vector numIslands2(int m, int n, vector>& positions) {
vector parent(m * n, -1);
vector res;
vector dx = {0, 1, 0, -1};
vector dy = {1, 0, -1, 0};
int count = 0;
auto find = [&](int i) {
if (parent[i] != i)
parent[i] = find(parent[i]);
return parent[i];
};
auto unionSet = [&](int x, int y) {
parent[find(y)] = find(x);
};
for (auto& pos : positions) {
int x = pos[0], y = pos[1];
int id = x * n + y;
if (parent[id] == -1) {
parent[id] = id;
count++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
int nid = nx * n + ny;
if (nx >= 0 && ny >= 0 && nx < m && ny < n && parent[nid] != -1) {
int root1 = find(id), root2 = find(nid);
if (root1 != root2) {
unionSet(root1, root2);
count--;
}
}
}
}
res.push_back(count);
}
return res;
}
