Share my Java code beating 84%. Using UnionFind, 2D->1D trick.

• use a counter to track the island.
every time put a 1 in the board, counter increase by one
every time when merging two island, counter decrease by one

running time: O(k)
union and find are const operations
time complexity: O(MN)

public class Solution {
private int[] p;
private int n;
private int count = 0;

private int find(int n){
if(p[n] != n)
p[n] = find(p[n]);
return p[n];
}
private void union(int a, int b){
if(!isInSameSet(a, b)){
p[find(a)] = p[find(b)];
count --;
}
}
private boolean isInSameSet(int a, int b){
return find(a) == find(b);
}

private int getLoc(int row, int col){
return row * n + col;
}

public List<Integer> numIslands2(int m, int n, int[][] pos) {
this.n = n;
p = new int[m * n];
for(int i = 0; i < p.length; i++)
p[i] = i;

int[][] b = new int[m][n];

List<Integer> res = new ArrayList<>();
for(int i = 0; i < pos.length; i++){
int row = pos[i][0], col = pos[i][1];
b[row][col] = 1;
count ++;
if(row - 1 >= 0 && b[row - 1][col] == 1)
union(getLoc(row, col), getLoc(row - 1, col));
if(row + 1 < m && b[row + 1][col] == 1)
union(getLoc(row, col), getLoc(row + 1, col));
if(col - 1 >= 0 && b[row][col - 1] == 1)
union(getLoc(row, col), getLoc(row, col - 1));
if(col + 1 < n && b[row][col + 1] == 1)
union(getLoc(row, col), getLoc(row, col + 1));