305. Number of Islands II

Problem Description

The task is to perform a series of land addition operations on a given 2D binary grid, which initially represents a map with all cells being water (denoted by 0s). We receive a list of positions that specify where land (1) should be added. Each operation may potentially connect with adjacent land to form or expand islands. An island is defined as a region of connected lands (horizontally or vertically), and each corner of the grid is considered surrounded by water. The problem requires us to return an array that reflects the number of distinct islands after each land addition operation.

Intuition

To efficiently track the changes and the number of islands as land cells are added, we can use the Union-Find algorithm. This algorithm is useful for keeping track of elements that are split into one or more disjoint sets and for merging these sets together.

Each cell in the 2D grid can be represented by a unique index in a 1D parent array (for instance, by mapping a cell (i, j) to an index i * n + j in the parent array). Initially, every cell is its own parent, indicating no connection to other cells.

The idea is to initially treat each new piece of land as a new island (incrementing the island count). Then, for each new land addition, we look at its neighboring cells (up, down, left, right) to check if any of them contains land. If a neighbor is also land, we find the root parent of both the current cell and the neighbor. If both have the same root parent, they are part of the same island; if they have different root parents, it means we have connected two previously separate islands, so we unite them under one parent and decrement our island counter since we're merging two islands into one.

This process repeats for each piece of land added, with the overall number of islands being adjusted accordingly. After each operation, the current number of islands is stored in the result array which is returned at the end.

The solution given above implements this approach. It keeps track of the parent array and the grid representation, updating both as land cells are added and connected. For each added land cell, it either creates a new island or merges existing islands, adjusting the total count and recording the state after each operation.

Learn more about Union Find patterns.

Solution Approach

The solution implements the Union-Find algorithm, which is efficient in handling dynamic connectivity queries. In this context, Union-Find helps to keep track of which pieces of land are connected to each other, thereby forming islands.

The main components of the algorithm are:

Parent array (p): A 1D array where the index represents a cell on the 2D grid, and the value represents the "parent" of that cell. Initially, each cell is its own parent.
Grid representation (grid): A 2D array reflecting the current state of the grid where land and water cells are represented by 1s and 0s respectively.

Steps Involved:

Initialization: Set up the parent array with each cell as its own parent and initialize the 2D grid array with zeros.

Find function (find): A function to determine the root parent of a cell. This is used to find the ultimate parent (or representative) of an element. If two elements have the same root parent, they belong to the same set (or island).

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

Adding land: Iterate over each position in the positions list, turning the corresponding water cell into land in the grid array.

Connecting islands: For each new land cell, increment the island count as it starts as a new island (cur += 1). Then, explore its four adjacent cells. If an adjacent cell is land, apply the find function to get the root parents for both the new land cell and its neighbor. If the root parents are different, it means that the new land addition has connected two separate islands and they should be united.

for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    if check(i + x, j + y) and find(i * n + j) != find((i + x) * n + j + y):
        p[find(i * n + j)] = find((i + x) * n + j + y)
        cur -= 1

Updating the result: After each land addition and potential island connections, the result (res) is appended with the current number of islands (cur).

The code ensures that land cells are not counted more than once by checking if the cell is already land before performing the union operations. If a position is already land, it continues to the next iteration without altering the island count.

By using Union-Find, the solution maintains an accurate count of islands after each operation and avoids recomputing the number of islands from scratch, resulting in a more efficient algorithm for the problem at hand.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example using the provided solution approach.

Consider a 3x3 grid, which is all water initially, and the positions to add land are [(0, 0), (0, 1), (1, 1), (2, 2)].

Initialization: The grid looks like this:
```
0 0 0
0 0 0
0 0 0
```
And we have a parent array of p for each cell, each initialized to their own index.
Adding land (0, 0): We start by turning the cell (0, 0) into land.
```
1 0 0
0 0 0
0 0 0
```
Island count cur is incremented to 1. Since there are no adjacent land cells, we move on to the next operation.
Adding land (0, 1): Then we add land to cell (0, 1).
```
1 1 0
0 0 0
0 0 0
```
cur becomes 2. We check adjacent cells and find that cell (0, 0) is land. Since cell (0, 1) is a new addition, their parents are different, and we perform a union. The find operation will update the parent of (0, 1) to be the same as (0, 0), and cur is decremented to 1.
Adding land (1, 1): Next, we add land at position (1, 1).
```
1 1 0
0 1 0
0 0 0
```
cur is increased to 2. We look at its neighbors and connect it with (0, 1). After the union with both (0, 1) and (1, 0), its parent will be updated, and cur will be decremented back to 1.
Adding land (2, 2): Finally, we add land to cell (2, 2).
```
1 1 0
0 1 0
0 0 1
```
cur increases to 2, and since the new land does not connect with existing land, the island count remains at 2. There are no union operations to perform here.

At each land addition, we append the current island count to the result array res, so after all operations, res would be [1, 1, 1, 2].

This illustrates the solution approach using the Union-Find algorithm to efficiently keep track of the number of islands after each land addition operation.

Solution Implementation

1class Solution:
2    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
3        parent = list(range(m * n))  # Initialize parent list for disjoint set
4        grid = [[0] * n for _ in range(m)]  # Initialize the grid with all water (0s)
5      
6        # Helper function to check if a position is within bounds and is land
7        def is_valid_land(i, j):
8            return 0 <= i < m and 0 <= j < n and grid[i][j] == 1
9      
10        # Find function for disjoint set with path compression
11        def find(x):
12            if parent[x] != x:
13                parent[x] = find(parent[x])  # Path compression
14            return parent[x]
15      
16        # List to record the number of islands after each addLand operation
17        num_islands_after_each_add_land = []
18        current_num_islands = 0  # Current number of islands
19      
20        for i, j in positions:
21            index = i * n + j  # Convert the 2D position to a 1D index for the disjoint set
22          
23            # If the land is already added, append the current number of islands and skip
24            if grid[i][j] == 1:
25                num_islands_after_each_add_land.append(current_num_islands)
26                continue
27              
28            grid[i][j] = 1  # Mark the position as land
29            current_num_islands += 1  # Increment island count by one
30            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # Check surrounding positions
31                neighbor_i = i + dx
32                neighbor_j = j + dy
33              
34                # If neighbor is valid land, merge sets if they are not already part of the same set
35                if is_valid_land(neighbor_i, neighbor_j):
36                    neighbor_index = neighbor_i * n + neighbor_j
37                    root = find(index)
38                    neighbor_root = find(neighbor_index)
39                    if root != neighbor_root:
40                        parent[root] = neighbor_root  # Union operation
41                        current_num_islands -= 1  # If two lands are connected, decrement island count
42                      
43            # Append the updated number of islands after this addLand operation
44            num_islands_after_each_add_land.append(current_num_islands)
45      
46        return num_islands_after_each_add_land
47

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    private int[] parent; // Parent array to represent the disjoint set (union-find structure)
6
7    // Function to calculate number of islands after each addLand operation.
8    public List<Integer> numIslands2(int m, int n, int[][] positions) {
9        parent = new int[m * n]; // Initialize union-find array, each node is its own parent at start.
10        Arrays.fill(parent, -1); // Fill with -1 to indicate water (uninhabited cell).
11      
12        int[][] grid = new int[m][n]; // Grid to maintain the state of the land and water.
13        int count = 0; // Island count.
14        List<Integer> answer = new ArrayList<>();
15        int[] directions = {-1, 0, 1, 0, -1}; // Directions for exploring adjacent cells.
16
17        // Iterate over the positions where we need to add land.
18        for (int[] pos : positions) {
19            int i = pos[0], j = pos[1];
20            int index = i * n + j; // Flatten the 2D position to 1D to use in union-find.
21
22            // If land is already present at the position, skip and record current island count.
23            if (grid[i][j] == 1) {
24                answer.add(count);
25                continue;
26            }
27
28            grid[i][j] = 1; // Mark the cell as land.
29            parent[index] = index; // Set itself as its parent since it's a new island.
30            count++; // Increment island count.
31
32            // Explore all 4 adjacent directions.
33            for (int k = 0; k < 4; ++k) {
34                int x = i + directions[k];
35                int y = j + directions[k + 1];
36                int adjacentIndex = x * n + y;
37
38                // If adjacent cell is within bounds, is land, and is not already unioned with the current cell.
39                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(adjacentIndex) != find(index)) {
40                    union(adjacentIndex, index); // Union the two cells.
41                    count--; // Decrement island count as we connected two islands.
42                }
43            }
44
45            answer.add(count); // Record the current count of islands.
46        }
47
48        return answer;
49    }
50
51    // Find operation using path compression.
52    private int find(int x) {
53        if (parent[x] != x) {
54            parent[x] = find(parent[x]);
55        }
56        return parent[x];
57    }
58
59    // Union operation to join two elements (here: cells of the grid).
60    private void union(int x, int y) {
61        int rootX = find(x);
62        int rootY = find(y);
63        if (rootX != rootY) {
64            parent[rootY] = rootX; // Make one root point to the other.
65        }
66    }
67}
68

1class Solution {
2public:
3    vector<int> parent; // 'parent' vector to hold the representative of each node's set
4
5    // Function to calculate the number of islands after each position is added
6    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
7        parent.resize(m * n); // Resize the parent vector to hold the union-find structure for the grid
8        // Initializing each node's parent to itself for union-find
9        for (int i = 0; i < parent.size(); ++i) parent[i] = i;
10      
11        vector<vector<int>> grid(m, vector<int>(n)); // A 2D grid to mark land positions
12        vector<int> ans; // Vector to store the result after each addition
13        int count = 0; // Counter to keep track of the islands count
14        // Array of directions to navigate neighbors
15        vector<int> directions = {-1, 0, 1, 0, -1};
16      
17        // Iterate through the provided positions
18        for (auto& pos : positions) {
19            int row = pos[0], col = pos[1];
20          
21            // Check if the current position is already land
22            if (grid[row][col] == 1) {
23                ans.push_back(count); // If it is, the number of islands doesn't change
24                continue;
25            }
26          
27            grid[row][col] = 1; // Mark the current position as land
28            ++count; // Increase the islands count as a new land has been added
29          
30            // Explore all 4 neighboring positions (up, down, left, and right)
31            for (int k = 0; k < 4; ++k) {
32                int x = row + directions[k], y = col + directions[k + 1];
33                // Check if the neighbor is valid and is land
34                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
35                    // If it is part of different islands, union them
36                    if (Find(x * n + y) != Find(row * n + col)) {
37                        Union(x * n + y, row * n + col);
38                        --count; // Decrease island count because of the union
39                    }
40                }
41            }
42          
43            ans.push_back(count); // Add the current count to the results
44        }
45      
46        return ans; // Return the result vector
47    }
48
49    // Function to find the representative of node 'x'
50    int Find(int x) {
51        if (parent[x] != x) parent[x] = Find(parent[x]); // Path compression
52        return parent[x];
53    }
54  
55    // Function to unite two subsets
56    void Union(int x, int y) {
57        int rootX = Find(x); // Find representative of x
58        int rootY = Find(y); // Find representative of y
59        // Only unite if the roots are different
60        if (rootX != rootY) {
61            parent[rootY] = rootX; // Make one root the parent of the other
62        }
63    }
64};
65

1let parent: number[] = []; // Array to hold the representative of each node's set
2
3// Function to calculate the number of islands after each position is added
4function numIslands2(m: number, n: number, positions: number[][]): number[] {
5  parent = new Array(m * n); // Initialize the parent array for the grid
6  // Set each node's initial parent to itself for the union-find structure
7  parent = parent.fill(0).map((_, index) => index);
8
9  let grid: number[][] = new Array(m); // A 2D grid to track land positions
10  for (let i = 0; i < m; i++) {
11    grid[i] = new Array(n).fill(0);
12  }
13
14  let ans: number[] = []; // Array to store the results after each addition
15  let count: number = 0; // Counter for number of islands
16  // Directions to navigate to the 4 possible neighbors: up, right, down, and left
17  let directions: number[] = [-1, 0, 1, 0, -1];
18
19  // Iterate through the list of positions to add
20  positions.forEach(([row, col]) => {
21    // Ensure the current position is not already marked as land
22    if (grid[row][col] === 1) {
23      ans.push(count); // Island count remains the same
24      return;
25    }
26
27    grid[row][col] = 1; // Mark the current position as land
28    count++; // Increment the island count for each new land piece
29
30    // Check all 4 neighboring cells
31    for (let k = 0; k < 4; k++) {
32      let x = row + directions[k];
33      let y = col + directions[k + 1];
34
35      // Check if the neighboring cell is within grid bounds and is land
36      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === 1) {
37        // Union the land pieces if they belong to different islands
38        if (find(x * n + y) !== find(row * n + col)) {
39          union(x * n + y, row * n + col);
40          count--; // Decrement the island count because they are now connected
41        }
42      }
43    }
44
45    // Push the current count of islands onto the results array
46    ans.push(count);
47  });
48
49  // Return the array holding the island count after each addition
50  return ans;
51}
52
53// Function to find the parent of node x
54function find(x: number): number {
55  if (parent[x] !== x) {
56    // Apply path compression by updating the parent entry
57    parent[x] = find(parent[x]);
58  }
59  return parent[x];
60}
61
62// Function to union two nodes if they belong to different parents
63function union(x: number, y: number): void {
64  let rootX: number = find(x);
65  let rootY: number = find(y);
66
67  if (rootX !== rootY) {
68    // Only perform the union if the roots are different
69    parent[rootY] = rootX; // Assign one root as the parent of the other
70  }
71}
72

Time and Space Complexity

The given code defines a class Solution with a method numIslands2 that maintains a dynamic list of the number of islands as new lands are added one by one. The algorithm uses Union-Find to group adjacent lands into a single island.

Time Complexity

The time complexity of this algorithm is primarily determined by the number of positions to process and the efficiency of the Union-Find operations. For each position added, the code checks its four adjacent cells (constant time) and potentially performs Union-Find operations.

Each find operation, in the worst case, is O(m * n), but with path compression (which is applied here), the amortized time complexity becomes near O(1).
Each cell is initially processed once and then may partake in up to 4 union operations if all its neighbors are lands.

Therefore, the overall time complexity can be seen as O(k * α(m * n)), where k is the number of positions and α denotes the Inverse Ackermann function, which grows very slowly and is practically considered a constant for all reasonable values of m and n.

Space Complexity

The space complexity is determined by the storage required for the grid and the parent array p.

The grid requires O(m * n) space to represent the entire grid.
The Union-Find structure p also requires O(m * n) space.

So the total space complexity of the algorithm is O(m * n), as both the grid and Union-Find structures are linear with respect to the size of the grid.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know