Facebook Pixel

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 (1s) 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. We initially increment the island count (assuming it's a new island)
  2. We check all four adjacent cells
  3. For each adjacent land cell that belongs to a different island (different root in Union-Find), we merge them and decrement the island count
  4. 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 where p[x] stores the parent of node x
  • size: array tracking the size of each component
  • find(x): finds the root of the component containing x, with path compression for optimization
  • union(a, b): merges two components and returns True if they were previously separate, False if already connected

2. Grid Initialization

  • Create a 2D grid of size m 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 current cnt to answer and continue

  • Add new land:

    • Set grid[i][j] = 1
    • Increment cnt by 1 (initially assume it's a new island)
  • Check adjacent cells: Use dirs = (-1, 0, 1, 0, -1) with pairwise to generate the four directions:

    • Calculate adjacent position: (x, y) = (i + a, j + b)
    • If the adjacent cell is:
      • Within bounds: 0 <= x < m and 0 <= y < n
      • Is land: grid[x][y] == 1
      • Not yet connected: uf.union(i * n + j, x * n + y) returns True
    • Then decrement cnt by 1 (two islands merge into one)
  • 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 Evaluator

Example 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 take O(α(m × n)) amortized time
    • The union operation itself (after finding roots) takes O(1)
    • Since we check at most 4 neighbors, this is O(4 × α(m × n)) = O(α(m × n))

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)
  • 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 effectively O(α(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 of i * 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
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More