This page explains Java solution to problem Number of Islands II
using Union Find
algorithm.
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 1:Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]
package com.vc.hard;
import java.util.*;
class NumberOfIslandsIi {
private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> res = new ArrayList<>();
int[] rootArr = new int[m * n];
int count = 0;
Arrays.fill(rootArr, -1);
for(int[] position: positions) {
int x = position[0];
int y = position[1];
int root = x * n + y;
if(rootArr[root] == -1) {
count++;
rootArr[root] = root;
for(int[] dir: dirs) {
int xNew = x + dir[0];
int yNew = y + dir[1];
int rootNeighbour = xNew * n + yNew;
if(xNew >= 0 && xNew < m && yNew >= 0 && yNew < n && rootArr[rootNeighbour] != -1) {
rootNeighbour = find(rootArr, rootNeighbour);
if(rootArr[root] != rootNeighbour) {
count--;
rootArr[rootNeighbour] = root;
}
}
}
}
res.add(count);
}
return res;
}
private int find(int[] rootArr, int root) {
if(rootArr[root] == root) return root;
else return find(rootArr, rootArr[root]);
}
}
O(K * log(M * N) Where
K is total number of positions to process
M is number of rows
N is number of cols
O(M * N) Where
M is number of rows
N is number of cols