305. Number of Islands II

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