Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/305.html
305. Number of Islands II
Level
Hard
Description
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
Follow up:
Can you do it in time complexity O(k log mn), where k is the length of the positions?
Algorithm
Union Find.
1 . Native UF
p = list(range(n))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
# union
p[find(a)] = find(b)
2 . UF with size
p = list(range(n))
size = [1] * n
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)
3 . UF with distance to root
p = list(range(n))
d = [0] * n
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
p[find(a)] = find(b)
d[find(a)] = distance
Algorithm - 2 - BFS
Each time a position is visited, first check whether the position is already a land cell.
- If so, add the current number of islands to the result list, and continue with the next position.
- Otherwise, check whether the position is adjacent to at least one land cell.
- If there is no adjacent land cell, then a new island is added, so add a greater island number to the result list, and update the new land cell with a new island number.
- Otherwise, find the minimum island number that is adjacent to the new land cell, do breadth first search on all cells adjacent to the new land cell, and update all reachable cells with the smallest island number. The number of islands may remain unchanged or decrease, and add the updated number of islands to the result list.
Finally, return the result list.
Code
-
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Number_of_Islands_II { int[][] dirs = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} }; public List<Integer> numIslands2(int m, int n, int[][] positions) { List<Integer> result = new ArrayList<>(); if(m <= 0 || n <= 0) { return result; } int count = 0; // number of islands // roots[c] = p means the parent of node c is p int[] roots = new int[m * n]; // one island = one tree Arrays.fill(roots, -1); for(int[] p : positions) { int root = n * p[0] + p[1]; // assume new point is isolated island roots[root] = root; // add new island count++; for(int[] dir : dirs) { // probe 4 directions int x = p[0] + dir[0]; int y = p[1] + dir[1]; int nb = n * x + y; if(x < 0 || x >= m || y < 0 || y >= n || roots[nb] == -1) { continue; } int rootNb = findIsland(roots, nb); if(root != rootNb) { // if neighbor is in another island roots[root] = rootNb; // union two islands root = rootNb; // current tree root = joined tree root count--; } } result.add(count); } return result; } public int findIsland(int[] roots, int id) { while(id != roots[id]) { id = roots[id]; } return id; } } // BFS class Solution { Set<Integer> set = new HashSet<Integer>(); public List<Integer> numIslands2(int m, int n, int[][] positions) { int[][] grid = new int[m][n]; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int length = positions.length; List<Integer> islands = new ArrayList<Integer>(); int islandsCount = 0; for (int i = 0; i < length; i++) { int[] position = positions[i]; int row = position[0], column = position[1]; if (grid[row][column] != 0) { islands.add(set.size()); continue; } int minAdjacent = Integer.MAX_VALUE; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n && grid[newRow][newColumn] != 0) minAdjacent = Math.min(minAdjacent, grid[newRow][newColumn]); } if (minAdjacent == Integer.MAX_VALUE) { set.add(islandsCount + 1); islandsCount++; grid[row][column] = islandsCount; } else { grid[row][column] = minAdjacent; breadthFirstSearch(grid, row, column); } islands.add(set.size()); } return islands; } public void breadthFirstSearch(int[][] grid, int row, int column) { int m = grid.length, n = grid[0].length; int curNumber = grid[row][column]; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; Queue<int[]> queue = new LinkedList<int[]>(); queue.offer(new int[]{row, column}); while (!queue.isEmpty()) { int[] square = queue.poll(); int curRow = square[0], curColumn = square[1]; for (int[] direction : directions) { int newRow = curRow + direction[0], newColumn = curColumn + direction[1]; if (newRow >= 0 && newRow < m && newColumn >= 0 && newColumn < n) { int prevNumber = grid[newRow][newColumn]; if (prevNumber > curNumber) { grid[newRow][newColumn] = curNumber; set.remove(prevNumber); queue.offer(new int[]{newRow, newColumn}); } } } } } } ############ class Solution { private int[] p; public List<Integer> numIslands2(int m, int n, int[][] positions) { p = new int[m * n]; for (int i = 0; i < p.length; ++i) { p[i] = i; } int[][] grid = new int[m][n]; int cnt = 0; List<Integer> ans = new ArrayList<>(); int[] dirs = {-1, 0, 1, 0, -1}; for (int[] pos : positions) { int i = pos[0]; int j = pos[1]; if (grid[i][j] == 1) { ans.add(cnt); continue; } grid[i][j] = 1; ++cnt; for (int k = 0; k < 4; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(x * n + y) != find(i * n + j)) { p[find(x * n + y)] = find(i * n + j); --cnt; } } ans.add(cnt); } return ans; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
class Solution { public: vector<int> p; vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) { p.resize(m * n); for (int i = 0; i < p.size(); ++i) p[i] = i; vector<vector<int>> grid(m, vector<int>(n)); vector<int> ans; int cnt = 0; vector<int> dirs = {-1, 0, 1, 0, -1}; for (auto& pos : positions) { int i = pos[0], j = pos[1]; if (grid[i][j] == 1) { ans.push_back(cnt); continue; } grid[i][j] = 1; ++cnt; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(x * n + y) != find(i * n + j)) { p[find(x * n + y)] = find(i * n + j); --cnt; } } ans.push_back(cnt); } return ans; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } }; -
class Solution: def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]: def check(i, j): return 0 <= i < m and 0 <= j < n and grid[i][j] == 1 def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(m * n)) grid = [[0] * n for _ in range(m)] res = [] cur = 0 for i, j in positions: if grid[i][j] == 1: # already counted, same as previous island count res.append(cur) continue grid[i][j] = 1 cur += 1 for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]: if check(i + x, j + y) and find(i * n + j) != find((i + x) * n + j + y): p[find(i * n + j)] = find((i + x) * n + j + y) cur -= 1 # 1 0 1 # 0 1 0 # for above, if setting 1st-row 2nd-col 0-to-1 # cur will -1 for 3 times # but cur += 1 after grid[i][j] = 1 so cur final result is 1 res.append(cur) return res ############ class UnionFind(object): def __init__(self, m, n): self.dad = [i for i in range(m * n)] self.rank = [0 for _ in range(m * n)] def find(self, x): if self.dad[x] != x: self.dad[x] = self.find(self.dad[x]) return self.dad[x] def union(self, xy): # xy is a tuple (x,y), with x and y value inside x, y = map(self.find, xy) if x == y: return False if self.rank[x] > self.rank[y]: self.dad[y] = x elif self.rank[x] < self.rank[y]: self.dad[x] = y else: self.dad[y] = x # search to the left, to find parent self.rank[x] += 1 # now x a parent, so +1 its rank return True class Solution(object): def numIslands2(self, m, n, positions): """ :type m: int :type n: int :type positions: List[List[int]] :rtype: List[int] """ uf = UnionFind(m, n) ans = 0 ret = [] dirs = [(0, -1), (0, 1), (1, 0), (-1, 0)] grid = set() for i, j in positions: ans += 1 grid |= {(i, j)} for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n and (ni, nj) in grid: if uf.union((ni * n + nj, i * n + j)): ans -= 1 ret.append(ans) return ret -
func numIslands2(m int, n int, positions [][]int) []int { p := make([]int, m*n) for i := 0; i < len(p); i++ { p[i] = i } grid := make([][]int, m) for i := 0; i < m; i++ { grid[i] = make([]int, n) } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } var ans []int cnt := 0 dirs := []int{-1, 0, 1, 0, -1} for _, pos := range positions { i, j := pos[0], pos[1] if grid[i][j] == 1 { ans = append(ans, cnt) continue } grid[i][j] = 1 cnt++ for k := 0; k < 4; k++ { x, y := i+dirs[k], j+dirs[k+1] if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && find(x*n+y) != find(i*n+j) { p[find(x*n+y)] = find(i*n + j) cnt-- } } ans = append(ans, cnt) } return ans }