# 305. 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:

``````Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]
``````

Explanation:

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
``````

Can you do it in time complexity O(k log mn), where k is the length of the `positions`?

0 0 0
0 0 0
0 0 0

1 0 0
0 0 0
0 0 0

1 0 1
0 0 0
0 0 0

1 1 1
0 0 0
0 0 0

1 1 1
0 1 0
0 0 0

``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<int> res;
int cnt = 0;
vector<int> roots(m * n, -1);
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
for (auto &pos : positions) {
int id = n * pos[0] + pos[1];
if (roots[id] != -1) {
res.push_back(cnt);
continue;
}
roots[id] = id;
++cnt;
for (auto dir : dirs) {
int x = pos[0] + dir[0], y = pos[1] + dir[1], cur_id = n * x + y;
if (x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1) continue;
int p = findRoot(roots, cur_id), q = findRoot(roots, id);
if (p != q) {
roots[p] = q;
--cnt;
}
}
res.push_back(cnt);
}
return res;
}
int findRoot(vector<int>& roots, int id) {
return (id == roots[id]) ? id : findRoot(roots, roots[id]);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/305

Number of Islands

https://leetcode.com/problems/number-of-islands-ii/

https://leetcode.com/problems/number-of-islands-ii/discuss/75470/Easiest-Java-Solution-with-Explanations

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation