305. Number of Islands II 🔒
Problem Description
You start with an m x n
grid that represents a map where all cells are initially water (represented by 0
). You can perform operations to add land (represented by 1
) to specific positions on this map.
Given an array positions
where positions[i] = [ri, ci]
represents the coordinates where you want to add land in the i-th operation, you need to track how many islands exist after each operation.
An island is defined as a group of adjacent land cells (1
s) that are connected horizontally or vertically. Land cells that are only diagonally adjacent do not form the same island. The entire grid is surrounded by water.
Your task is to return an array answer
where answer[i]
represents the total number of islands present in the grid after performing the i-th operation (adding land at position [ri, ci]
).
For example:
- If you add land to an isolated water cell, you create a new island (island count increases by 1)
- If you add land adjacent to existing land, you extend that island (island count stays the same)
- If you add land between two or more separate islands, you connect them into one island (island count decreases)
- If you try to add land to a position that's already land, nothing changes (island count stays the same)
The solution uses a Union-Find data structure to efficiently track and merge islands as land is added. Each position in the grid is mapped to a unique index i * n + j
for use in the union-find structure. When adding new land, the algorithm checks all four adjacent cells and merges connected components as needed, updating the island count accordingly.
Intuition
The key insight is recognizing that this is a dynamic connectivity problem. As we add land pieces one by one, we need to efficiently track which land cells belong to the same island and update the total island count.
Initially, when we add a land cell to water, we create a new island. But the complexity arises when this new land cell is adjacent to existing land cells. If it's next to one existing island, it simply becomes part of that island. If it's adjacent to multiple separate islands, it acts as a bridge that merges them into one.
Think of it like dropping stones into water - each stone initially forms its own "island". But if you drop a stone next to an existing stone, they form one larger island. If you drop a stone between two separate groups of stones, all three merge into one island.
The challenge is efficiently tracking these merging operations. A naive approach would be to run a full island counting algorithm (like DFS or BFS) after each land addition, but this would be too slow for large grids with many operations.
This naturally leads us to Union-Find (Disjoint Set Union), a data structure specifically designed for tracking connected components that can merge over time. Each land cell can be treated as a node, and adjacent land cells should belong to the same set (island).
When we add new land:
- We initially increment the island count (assuming it's a new island)
- We check all four adjacent cells
- For each adjacent land cell that belongs to a different island (different root in Union-Find), we merge them and decrement the island count
- If the adjacent land already belongs to the same island as our new cell, no count change is needed
The Union-Find structure with path compression and union by size ensures near-constant time operations, making this approach efficient even for large grids with many position updates.
Solution Approach
The solution uses a Union-Find data structure to efficiently track and merge islands. Let's walk through the implementation step by step:
1. Union-Find Data Structure Setup
We create a UnionFind
class that maintains:
p
: parent array wherep[x]
stores the parent of nodex
size
: array tracking the size of each componentfind(x)
: finds the root of the component containingx
, with path compression for optimizationunion(a, b)
: merges two components and returnsTrue
if they were previously separate,False
if already connected
2. Grid Initialization
- Create a 2D
grid
of sizem x n
, initially all zeros (water) - Initialize
cnt = 0
to track the current number of islands - Create a Union-Find instance with
m * n
nodes (one for each grid cell)
3. Position Mapping
Each grid position (i, j)
is mapped to a unique index using the formula i * n + j
. This allows us to use a 1D Union-Find structure for a 2D grid.
4. Processing Each Position
For each position (i, j)
in positions
:
-
Check if already land: If
grid[i][j] == 1
, this position is already land, so append currentcnt
to answer and continue -
Add new land:
- Set
grid[i][j] = 1
- Increment
cnt
by 1 (initially assume it's a new island)
- Set
-
Check adjacent cells: Use
dirs = (-1, 0, 1, 0, -1)
withpairwise
to generate the four directions:- Calculate adjacent position:
(x, y) = (i + a, j + b)
- If the adjacent cell is:
- Within bounds:
0 <= x < m
and0 <= y < n
- Is land:
grid[x][y] == 1
- Not yet connected:
uf.union(i * n + j, x * n + y)
returnsTrue
- Within bounds:
- Then decrement
cnt
by 1 (two islands merge into one)
- Calculate adjacent position:
-
Record result: Append current
cnt
to the answer array
5. Union Operation Details
The union
operation in the Union-Find:
- Takes indices adjusted by subtracting 1 (to handle 0-based indexing)
- Finds roots of both components using
find
- If they share the same root, returns
False
(already connected) - Otherwise, merges the smaller component into the larger one (union by size optimization)
- Returns
True
to indicate a successful merge
The time complexity is O(k × α(m × n))
where k
is the number of positions and α
is the inverse Ackermann function (practically constant). The space complexity is O(m × n)
for the grid and Union-Find structure.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example with a 3×3 grid and positions = [[0,0], [0,1], [1,1], [2,1], [1,0]].
Initial State:
Grid: Islands: 0 . . . . . . . . .
Operation 1: Add land at [0,0]
- Grid[0][0] = 0 (water), so we add land
- Increment island count: 0 → 1
- Check 4 neighbors: all are water
- No unions needed
- Result: 1 island
Grid: Islands: 1 1 . . . . . . . .
Operation 2: Add land at [0,1]
- Grid[0][1] = 0 (water), so we add land
- Increment island count: 1 → 2
- Check neighbors:
- Left [0,0] is land! Union(1, 0) returns True
- Decrement count: 2 → 1
- Result: 1 island (merged with existing)
Grid: Islands: 1 1 1 . . . . . . .
Operation 3: Add land at [1,1]
- Grid[1][1] = 0 (water), so we add land
- Increment island count: 1 → 2
- Check neighbors:
- Up [0,1] is land! Union(4, 1) returns True
- Decrement count: 2 → 1
- Result: 1 island (extended the existing island)
Grid: Islands: 1 1 1 . . 1 . . . .
Operation 4: Add land at [2,1]
- Grid[2][1] = 0 (water), so we add land
- Increment island count: 1 → 2
- Check neighbors:
- Up [1,1] is land! Union(7, 4) returns True
- Decrement count: 2 → 1
- Result: 1 island (still one connected island)
Grid: Islands: 1 1 1 . . 1 . . 1 .
Operation 5: Add land at [1,0]
- Grid[1][0] = 0 (water), so we add land
- Increment island count: 1 → 2
- Check neighbors:
- Up [0,0] is land! Union(3, 0) returns True
- Decrement count: 2 → 1
- Right [1,1] is land! Union(3, 4) returns False (already connected through [0,0]→[0,1]→[1,1])
- No decrement since they're already in the same component
- Result: 1 island
Grid: Islands: 1 1 1 . 1 1 . . 1 .
Final Answer: [1, 1, 1, 1, 1]
The key insight is how Union-Find efficiently tracks connectivity. When we try to union [1,0] with [1,1] in the last step, they're already connected through the path [1,0]→[0,0]→[0,1]→[1,1], so union returns False and we don't double-count the merge.
Solution Implementation
1class UnionFind:
2 """Union-Find (Disjoint Set Union) data structure with path compression and union by size."""
3
4 def __init__(self, n: int):
5 """Initialize Union-Find with n elements (0 to n-1)."""
6 self.parent = list(range(n)) # Each element is initially its own parent
7 self.size = [1] * n # Size of each component initially 1
8
9 def find(self, x: int) -> int:
10 """Find the root of element x with path compression."""
11 if self.parent[x] != x:
12 # Path compression: make x point directly to root
13 self.parent[x] = self.find(self.parent[x])
14 return self.parent[x]
15
16 def union(self, a: int, b: int) -> bool:
17 """
18 Union two elements a and b.
19 Returns True if they were in different components, False otherwise.
20 """
21 root_a = self.find(a)
22 root_b = self.find(b)
23
24 # Already in the same component
25 if root_a == root_b:
26 return False
27
28 # Union by size: attach smaller tree under larger tree
29 if self.size[root_a] > self.size[root_b]:
30 self.parent[root_b] = root_a
31 self.size[root_a] += self.size[root_b]
32 else:
33 self.parent[root_a] = root_b
34 self.size[root_b] += self.size[root_a]
35
36 return True
37
38
39class Solution:
40 def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
41 """
42 Given a m x n grid initially filled with water, return the number of islands
43 after each land addition from positions.
44
45 Args:
46 m: Number of rows in the grid
47 n: Number of columns in the grid
48 positions: List of [row, col] positions where land is added
49
50 Returns:
51 List containing number of islands after each addition
52 """
53 # Initialize Union-Find for m*n grid cells
54 uf = UnionFind(m * n)
55
56 # Track which cells are land (1) or water (0)
57 grid = [[0] * n for _ in range(m)]
58
59 # Result list to store island count after each addition
60 result = []
61
62 # Direction vectors for 4-directional movement (up, right, down, left)
63 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
64
65 # Current number of islands
66 island_count = 0
67
68 for row, col in positions:
69 # If this position is already land, no change in island count
70 if grid[row][col] == 1:
71 result.append(island_count)
72 continue
73
74 # Mark this position as land
75 grid[row][col] = 1
76 # Initially, this creates a new island
77 island_count += 1
78
79 # Check all 4 adjacent cells
80 for dx, dy in directions:
81 new_row, new_col = row + dx, col + dy
82
83 # Check if adjacent cell is valid and is land
84 if (0 <= new_row < m and
85 0 <= new_col < n and
86 grid[new_row][new_col] == 1):
87
88 # Convert 2D coordinates to 1D index for Union-Find
89 current_idx = row * n + col
90 adjacent_idx = new_row * n + new_col
91
92 # If union is successful (they were in different components),
93 # we've merged two islands into one
94 if uf.union(current_idx, adjacent_idx):
95 island_count -= 1
96
97 result.append(island_count)
98
99 return result
100
1/**
2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size
3 */
4class UnionFind {
5 private final int[] parent; // parent[i] = parent of node i
6 private final int[] size; // size[i] = size of the subtree rooted at i
7
8 /**
9 * Initialize Union-Find structure with n elements (0 to n-1)
10 * @param n number of elements
11 */
12 public UnionFind(int n) {
13 parent = new int[n];
14 size = new int[n];
15
16 // Initially, each element is its own parent (separate component)
17 for (int i = 0; i < n; i++) {
18 parent[i] = i;
19 size[i] = 1;
20 }
21 }
22
23 /**
24 * Find the root of the component containing element x
25 * Uses path compression for optimization
26 * @param x element to find root for
27 * @return root of the component containing x
28 */
29 public int find(int x) {
30 // Path compression: make every node point directly to root
31 if (parent[x] != x) {
32 parent[x] = find(parent[x]);
33 }
34 return parent[x];
35 }
36
37 /**
38 * Union two components containing elements a and b
39 * Uses union by size for optimization
40 * @param a first element
41 * @param b second element
42 * @return true if union was performed (components were different), false otherwise
43 */
44 public boolean union(int a, int b) {
45 int rootA = find(a);
46 int rootB = find(b);
47
48 // Already in the same component
49 if (rootA == rootB) {
50 return false;
51 }
52
53 // Union by size: attach smaller tree under larger tree
54 if (size[rootA] > size[rootB]) {
55 parent[rootB] = rootA;
56 size[rootA] += size[rootB];
57 } else {
58 parent[rootA] = rootB;
59 size[rootB] += size[rootA];
60 }
61
62 return true;
63 }
64}
65
66/**
67 * Solution for Number of Islands II problem
68 * Dynamically adds land positions and tracks the number of islands
69 */
70class Solution {
71 /**
72 * Given a grid initially filled with water, add land at given positions
73 * and return the number of islands after each addition
74 * @param m number of rows in the grid
75 * @param n number of columns in the grid
76 * @param positions array of [row, col] positions where land is added
77 * @return list containing number of islands after each position is added
78 */
79 public List<Integer> numIslands2(int m, int n, int[][] positions) {
80 // Grid to track land (1) and water (0)
81 int[][] grid = new int[m][n];
82
83 // Union-Find to manage connected components
84 // Each cell (i,j) is mapped to index i*n + j
85 UnionFind unionFind = new UnionFind(m * n);
86
87 // Direction vectors for 4-directional movement (up, right, down, left)
88 int[] directions = {-1, 0, 1, 0, -1};
89
90 // Current count of islands
91 int islandCount = 0;
92
93 // Result list to store island count after each position
94 List<Integer> result = new ArrayList<>();
95
96 // Process each position
97 for (int[] position : positions) {
98 int row = position[0];
99 int col = position[1];
100
101 // Skip if this position already has land
102 if (grid[row][col] == 1) {
103 result.add(islandCount);
104 continue;
105 }
106
107 // Add land at current position
108 grid[row][col] = 1;
109 islandCount++; // Initially, this forms a new island
110
111 // Check all 4 adjacent cells
112 for (int k = 0; k < 4; k++) {
113 int newRow = row + directions[k];
114 int newCol = col + directions[k + 1];
115
116 // Check if adjacent cell is valid and has land
117 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
118 grid[newRow][newCol] == 1) {
119
120 // Try to union current cell with adjacent land cell
121 // Convert 2D coordinates to 1D index for Union-Find
122 int currentIndex = row * n + col;
123 int adjacentIndex = newRow * n + newCol;
124
125 // If union successful (they were in different components),
126 // decrease island count
127 if (unionFind.union(currentIndex, adjacentIndex)) {
128 islandCount--;
129 }
130 }
131 }
132
133 // Add current island count to result
134 result.add(islandCount);
135 }
136
137 return result;
138 }
139}
140
1class UnionFind {
2public:
3 // Initialize Union-Find data structure with n elements
4 UnionFind(int n) {
5 parent = vector<int>(n);
6 componentSize = vector<int>(n, 1);
7 // Initially, each element is its own parent (self-loop)
8 iota(parent.begin(), parent.end(), 0);
9 }
10
11 // Unite two components containing elements a and b
12 // Returns true if they were in different components, false otherwise
13 bool unite(int a, int b) {
14 int rootA = find(a);
15 int rootB = find(b);
16
17 // Already in the same component
18 if (rootA == rootB) {
19 return false;
20 }
21
22 // Union by size: attach smaller tree under root of larger tree
23 if (componentSize[rootA] > componentSize[rootB]) {
24 parent[rootB] = rootA;
25 componentSize[rootA] += componentSize[rootB];
26 } else {
27 parent[rootA] = rootB;
28 componentSize[rootB] += componentSize[rootA];
29 }
30
31 return true;
32 }
33
34 // Find the root of the component containing element x
35 // Uses path compression for optimization
36 int find(int x) {
37 if (parent[x] != x) {
38 parent[x] = find(parent[x]); // Path compression
39 }
40 return parent[x];
41 }
42
43private:
44 vector<int> parent; // Parent array for Union-Find
45 vector<int> componentSize; // Size of each component for union by size
46};
47
48class Solution {
49public:
50 vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
51 // Initialize grid to track land cells
52 int grid[m][n];
53 memset(grid, 0, sizeof(grid));
54
55 // Create Union-Find structure for all possible cells
56 UnionFind unionFind(m * n);
57
58 // Direction vectors for exploring 4 adjacent cells (up, right, down, left)
59 int directions[5] = {-1, 0, 1, 0, -1};
60
61 // Counter for number of islands
62 int islandCount = 0;
63
64 // Result vector to store island count after each operation
65 vector<int> result;
66
67 // Process each position to add land
68 for (auto& position : positions) {
69 int row = position[0];
70 int col = position[1];
71
72 // If this cell is already land, no change in island count
73 if (grid[row][col]) {
74 result.push_back(islandCount);
75 continue;
76 }
77
78 // Mark this cell as land
79 grid[row][col] = 1;
80
81 // Initially, this creates a new island
82 ++islandCount;
83
84 // Check all 4 adjacent cells
85 for (int k = 0; k < 4; ++k) {
86 int newRow = row + directions[k];
87 int newCol = col + directions[k + 1];
88
89 // Check if adjacent cell is valid and is land
90 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol]) {
91 // Convert 2D coordinates to 1D for Union-Find
92 int currentCell = row * n + col;
93 int adjacentCell = newRow * n + newCol;
94
95 // If unite returns true, two separate islands were merged
96 if (unionFind.unite(currentCell, adjacentCell)) {
97 --islandCount;
98 }
99 }
100 }
101
102 // Store the current island count
103 result.push_back(islandCount);
104 }
105
106 return result;
107 }
108};
109
1// Parent array for Union-Find structure
2let parent: number[];
3// Size array for union by rank optimization
4let size: number[];
5
6/**
7 * Find operation with path compression
8 * Returns the root parent of element x
9 */
10function find(x: number): number {
11 if (parent[x] !== x) {
12 // Path compression: make x point directly to root
13 parent[x] = find(parent[x]);
14 }
15 return parent[x];
16}
17
18/**
19 * Union operation with union by rank
20 * Merges two sets containing elements a and b
21 * Returns true if union was performed, false if already in same set
22 */
23function union(a: number, b: number): boolean {
24 const rootA = find(a);
25 const rootB = find(b);
26
27 // Already in the same set
28 if (rootA === rootB) {
29 return false;
30 }
31
32 // Union by rank: attach smaller tree under larger tree
33 if (size[rootA] > size[rootB]) {
34 parent[rootB] = rootA;
35 size[rootA] += size[rootB];
36 } else {
37 parent[rootA] = rootB;
38 size[rootB] += size[rootA];
39 }
40
41 return true;
42}
43
44/**
45 * Counts number of islands after adding land positions one by one
46 * @param m - number of rows in the grid
47 * @param n - number of columns in the grid
48 * @param positions - array of [row, col] positions where land is added
49 * @returns array where each element is the number of islands after adding each position
50 */
51function numIslands2(m: number, n: number, positions: number[][]): number[] {
52 // Initialize 2D grid to track land cells (1 = land, 0 = water)
53 const grid: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
54
55 // Initialize Union-Find structure for m*n cells
56 const totalCells = m * n;
57 parent = Array(totalCells).fill(0).map((_, index) => index);
58 size = Array(totalCells).fill(1);
59
60 // Result array to store island count after each operation
61 const result: number[] = [];
62
63 // Direction vectors for exploring 4 adjacent cells (up, right, down, left)
64 const directions: number[] = [-1, 0, 1, 0, -1];
65
66 // Current number of islands
67 let islandCount = 0;
68
69 // Process each position
70 for (const [row, col] of positions) {
71 // Skip if this position was already added as land
72 if (grid[row][col] === 1) {
73 result.push(islandCount);
74 continue;
75 }
76
77 // Mark current position as land
78 grid[row][col] = 1;
79 // Initially, adding land creates a new island
80 islandCount++;
81
82 // Check all 4 adjacent cells
83 for (let k = 0; k < 4; k++) {
84 const newRow = row + directions[k];
85 const newCol = col + directions[k + 1];
86
87 // Skip if out of bounds or not land
88 if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || grid[newRow][newCol] === 0) {
89 continue;
90 }
91
92 // Try to union current cell with adjacent land cell
93 // Convert 2D coordinates to 1D index: row * n + col
94 const currentIndex = row * n + col;
95 const adjacentIndex = newRow * n + newCol;
96
97 // If union successful (they were in different sets), decrease island count
98 if (union(currentIndex, adjacentIndex)) {
99 islandCount--;
100 }
101 }
102
103 // Add current island count to result
104 result.push(islandCount);
105 }
106
107 return result;
108}
109
Time and Space Complexity
Time Complexity: O(k × α(m × n))
where k
is the length of positions
and α
is the inverse Ackermann function.
- For each position in
positions
(k iterations total):- Checking if the cell is already land:
O(1)
- Adding the land and incrementing count:
O(1)
- Checking up to 4 adjacent cells and performing union operations if needed
- Each union operation involves two
find
operations and the actual union - With path compression and union by size,
find
operations takeO(α(m × n))
amortized time - The
union
operation itself (after finding roots) takesO(1)
- Since we check at most 4 neighbors, this is
O(4 × α(m × n))
=O(α(m × n))
- Checking if the cell is already land:
The inverse Ackermann function α(m × n)
grows extremely slowly and can be considered effectively constant for all practical values of m × n
(it's less than 5 for any reasonable input size).
Space Complexity: O(m × n)
- The UnionFind data structure maintains:
- Parent array
p
:O(m × n)
- Size array
size
:O(m × n)
- Parent array
- The
grid
matrix to track land cells:O(m × n)
- The
ans
list to store results:O(k)
- Recursive call stack for
find
operation:O(log(m × n))
in worst case before path compression, but effectivelyO(α(m × n))
with path compression
Overall space complexity is dominated by O(m × n)
for the UnionFind structure and grid.
Common Pitfalls
1. Duplicate Position Handling
One of the most common mistakes is not properly handling duplicate positions in the input. If the same position [r, c]
appears multiple times in the positions
array, adding land to an already-land cell should not change the island count.
Incorrect approach:
for row, col in positions: grid[row][col] = 1 island_count += 1 # Check neighbors and union...
Correct approach:
for row, col in positions: if grid[row][col] == 1: # Already land result.append(island_count) continue grid[row][col] = 1 island_count += 1 # Check neighbors and union...
2. Incorrect Index Mapping for Union-Find
When converting 2D grid coordinates to 1D Union-Find indices, using the wrong formula can cause incorrect unions between unrelated cells.
Common mistakes:
- Using
i + j * m
instead ofi * n + j
- Mixing up row/column dimensions
- Off-by-one errors when the Union-Find is 1-indexed
Correct formula:
# For 0-indexed Union-Find current_idx = row * n + col # n is number of columns adjacent_idx = new_row * n + new_col
3. Forgetting to Decrement Island Count After Union
When two separate islands are connected by adding new land, the total island count should decrease. A common mistake is to only increment the count when adding new land but forget to decrement when merging islands.
Incorrect:
island_count += 1 # New land added if uf.union(current_idx, adjacent_idx): # Forgot to decrement! pass
Correct:
island_count += 1 # New land added if uf.union(current_idx, adjacent_idx): island_count -= 1 # Two islands merged into one
4. Union-Find Return Value Misunderstanding
The union
method should return True
only when two previously separate components are merged, not just when the union operation is called.
Incorrect union implementation:
def union(self, a: int, b: int) -> bool:
root_a = self.find(a)
root_b = self.find(b)
self.parent[root_b] = root_a
return True # Always returns True!
Correct implementation:
def union(self, a: int, b: int) -> bool:
root_a = self.find(a)
root_b = self.find(b)
if root_a == root_b:
return False # Already connected
# Perform union...
return True # Successfully merged two components
5. Boundary Checking Errors
Failing to properly check grid boundaries when examining adjacent cells can lead to index out of bounds errors or incorrect connections.
Common boundary check mistakes:
- Using
<= m
instead of< m
- Checking only one dimension
- Wrong order of conditions causing short-circuit evaluation issues
Correct boundary check:
if (0 <= new_row < m and 0 <= new_col < n and grid[new_row][new_col] == 1): # Process valid land neighbor
Which technique can we use to find the middle of a linked list?
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!