Java solution with union-find class


  • 0
    M

    Runtime of union() and find(): O(k), k is the height of tree, worst case is n.

    public class Solution {
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            List<Integer> list = new ArrayList<>();
            UF2D uf = new UF2D(m, n);
            for(int[] p : positions){
                int x = uf.getIndex(p[0], p[1]);
                boolean repeat = !uf.add(x); // add() return false means repeat
                if(repeat) continue;
                for(int[] dir : dirs){
                    int ni=p[0]+dir[0], nj=p[1]+dir[1]; //neighbor_i, neighbor_j
                    int y = uf.getIndex(ni, nj);
                    if(!uf.isLand(y)) continue; //ni, nj out of border or not land 
                    uf.union(x, y);
                }
                list.add(uf.count());
            }
            return list;
        }
        
        class UF2D{
            private int[] uf;
            private int m, n;  
            private int count = 0;
            
            public UF2D(int m, int n){
                this.m = m;
                this.n = n;
                uf = new int[m*n+1];
            }
            // all index > 0
            public int getIndex(int i, int j) { 
                if (i < 0 || j < 0 || i >= m || j >= n) return 0;
                return i*n + j + 1; 
            }
            public boolean add(int i) {
                if(uf[i] == i) return false;
                uf[i] = i;
                count++;
                return true;
            }
            public void union(int x, int y){
                int xx = find(x);
                int yy = find(y);
                if(xx == yy) return;
                uf[xx] = yy;
                count--;
            }
            private int find(int i){
                if(uf[i] == i) return i;
                uf[i] = find(uf[i]);
                return uf[i];
            }
            public int count(){
                return count;
            }
            public boolean isLand(int i){
                return uf[i] != 0;
            }
        }
        
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.