Number of Islands II

A 2d grid map of

`m`

rows and`n`

columns is initially filled with water. We may perform anaddLandoperation 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. 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.addLandoperation

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 0Operation #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 0Operation #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 0Operation #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 0Operation #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 0We return the result as an array:

`[1, 1, 2, 3]`

Update: (2015/11/13)

If you are usingJava, 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; } };