Number of Islands II

Problem Statement

In this problem, you are presented with a 2D grid simulation where initially, all cells are filled with water (represented by '0'). This grid has dimensions m by n. As part of the simulation, you are tasked with performing a series of operations where specific cells in the grid are transformed from water (0) to land (1). This task is guided by a series of positions, where each position specifies the row and column of the cell to be transformed.

Your goal is to determine the number of distinct islands present in the grid after each transformation operation. An "island" is defined as a cluster of adjacent lands (1's) connected either horizontally or vertically. It's also important to remember that the grid is surrounded entirely by water, isolating any potential land cells within from the edges.

Thus, for each position in the provided array positions, you will convert the specified cell to land and then have to count and return the number of connected groups of land cells (islands) after this transformation.

Examples

Example 1

Input:

m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]

Output:

[1,1,2,3]

Explanation:

Initially, the 2d grid is filled with water.
- Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land. We have 3 islands.

Example 2

Input:

m = 1, n = 1, positions = [[0,0]]

Output:

[1]

Constraints

• 1 <= m, n, positions.length <= 104
• 1 <= m * n <= 104
• positions[i].length == 2
• 0 <= ri < m
• 0 <= ci < n

Approach and Intuition

To tackle this problem efficiently, we need an appropriate data structure that allows union-find operations. Both union and find are critical to efficiently determine whether adjacent cells are part of the same island or if they form a new island when a cell turns into land.

1. Initial Setup:

   • Initialize the grid of size m x n with all values set to zero (water).
   • Prepare a union-find (disjoint set) structure to help manage and merge islands efficiently. Each cell has a unique identifier based on its row and column.

2. Processing Operations:

   • For each operation, convert the specified cell into land if it's not already land.
   • For each newly converted land cell, check its four possible neighboring cells (up, down, left, right):
     • If a neighboring cell is land, use the union operation to merge the sets, thus connecting components into a single island.

3. Counting Islands:

   • After processing each operation, use the disjoint set structure to count the number of distinct sets (islands).
   • Keep track of these counts and append to the result array.

4. Consider Edge Cases:

   • Single cell grids where the output is straightforward with one transformation resulting in one island.
   • Repetitive or consecutive operations on the same cell don't increase the number of islands.
   • Large grids reaching the upper constraint limits should be handled efficiently without timeouts, validating the importance of the union-find structure’s nearly constant time operations.

By following this process, we can incrementally build up the grid's structure from water to land, efficiently merging islands and counting them as they form, which satisfies the problem requirements given by various operation constraints.

Solutions

class DisjointSet {
private:
    vector<int> root, size;
    int islands;
    
public:
    DisjointSet(int capacity) {
        root.resize(capacity, -1);
        size.resize(capacity, 0);
        islands = 0;
    }
    
    void plow(int i) {
        if (root[i] != -1) return;
        root[i] = i;
        islands++;
    }
    
    bool checkPlowed(int i) {
        return root[i] != -1;
    }
    
    int countIslands() { return islands; }
    
    int locate(int i) {
        if (root[i] != i) {
            root[i] = locate(root[i]);
        }
        return root[i];
    }
    
    void link(int i, int j) {
        int rootI = locate(i), rootJ = locate(j);
        if (rootI == rootJ) {
            return;
        } else if (size[rootI] < size[rootJ]) {
            root[rootI] = rootJ;
        } else if (size[rootI] > size[rootJ]) {
            root[rootJ] = rootI;
        } else {
            root[rootJ] = rootI;
            size[rootI]++;
        }
        islands--;
    }
};
    
class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        vector<int> dirX = {-1, 1, 0, 0};
        vector<int> dirY = {0, 0, -1, 1};
        DisjointSet dsu(m * n);
        vector<int> solution;
    
        for (auto& pos : positions) {
            int cell = pos[0] * n + pos[1];
            dsu.plow(cell);
    
            for (int d = 0; d < 4; d++) {
                int adjX = pos[0] + dirX[d];
                int adjY = pos[1] + dirY[d];
                int neighborCell = adjX * n + adjY;
                    
                if (adjX >= 0 && adjX < m && adjY >= 0 && adjY < n && dsu.checkPlowed(neighborCell)) {
                    dsu.link(cell, neighborCell);
                }
            }
            solution.push_back(dsu.countIslands());
        }
        return solution;
    }
};