Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Update: (2015/11/13)
If you are using Java, the parameter List<int[]> positions had been changed to int[][] positions. Please click on the reload button above the code editor to reset the code definition.

Use unionset algorithm.

Take care of the index checking, since I compress the 2d matrix to 1d array.

class Solution {
public:
    vector<int> ans; // overflow?
    vector<int> unionset; // overflow?
    unordered_set<int> roots;
        
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        ans.clear();
        roots.clear();
        unionset = vector<int>(m*n, -1);// connect all water cells to root -1
        int dict[] = {-1, 1, -n, n};
        for(auto it = positions.begin(); it != positions.end(); it++){
            int idx = it->first * n + it->second;
            if(unionset[idx] != -1){
                // not a water cell
                // num of island do not change
                ans.push_back(roots.size());
            }
            else{
                // find neighbours, try to merge
                set(idx, idx);
                roots.insert(idx);
                for(int i = 0; i < 4; i++){
                    int nidx = idx + dict[i];
                    // not a valid neighbour
                    if(nidx < 0 || nidx >= m * n || ((nidx / n != idx / n) && (nidx % n != idx % n))){ // previously a BUG HERE
                        continue;
                    }
                    // neighbour is a water cell
                    if(unionset[nidx] == -1){
                        continue;
                    }
                    int root = find(nidx);
                    if(root != idx){
                        set(root, idx);
                        roots.erase(root);    
                    }
                    
                }
            }
            ans.push_back(roots.size());
        }
        return ans;
    }
    int find(int idx){
        //base condition
        if(unionset[idx] == idx){
            return idx;
        }
        else{
            int root = find(unionset[idx]);
            unionset[idx] = root;
            return root;
        }
    }
    void set(int idx, int root){
        unionset[idx] = root;
    }
};