Clean Java solution using union find


  • 0
    J

    The solution is inspired by the following tutorial of union find. Easy to implement:

    Union-Find Algorithms

    	class QuickUnion {
    		private int[] id;
    		private int[] size;
    		int m,n;		
    		int island;
    		
    		public QuickUnion(int m, int n) {
    			this.m = m;
    			this.n = n;
    			id = new int[m * n];
    			size = new int[m * n];
    			island = 0;
    		}
    		
    		//Get the root for index i (root is the representative)
    		private int root(int i) {
    			while (i != id[i]) {
    				id[i] = id[id[i]];  //Path compression
    				i = id[i];
    			}
    			return i;
    		}
    		
    		//Get the component size, if the size is 0 then we don't have an island yet.
    		public int getSize(int x, int y) {
    			return size[getIndex(x, y)];
    		}
    
    		private int getIndex(int x, int y) {
    			return x * n + y;
    		}
    		
    		public void addIsland(int x, int y) {
    			int p = getIndex(x, y);
    			if (size[p] != 0) return;
    			size[p] = 1;
    			id[p] = p;
    			island++;
    		}
    		
    		public void unite(int x1, int y1, int x2, int y2) {
    			unite(getIndex(x1, y1), getIndex(x2, y2));
    		}
    		
    		private void unite(int p, int q) {
    			int i = root(p);
    			int j = root(q);			
    			if (i != j) island--;  //If we are merging two different islands, then island count decreases.
    			if (size[i] < size[j]) {
    				id[i] = j;
    				size[j] += size[i];
    			}
    			else {
    				id[j] = i;
    				size[i] += size[j];
    			}
    		}
    	}
    	
    	
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
        	QuickUnion union = new QuickUnion(m,n);
        	int[] dx = {1,0,-1,0};
        	int[] dy = {0,1,0,-1};
        	List<Integer> result = new ArrayList<Integer>();
        	for (int[] pos : positions) {
        		int x = pos[0];
        		int y = pos[1];
        		union.addIsland(x, y);
        		for (int i = 0; i < 4; i++) {
        			int newX = x + dx[i];
        			int newY = y + dy[i];
        			if (newX < 0 || newY < 0 || newX >= m || newY >= n) continue;
        			if (union.getSize(newX, newY) == 0) continue;
        			union.unite(x, y, newX, newY);    			
        		}
        		result.add(union.island);
        	}
        	return result;
        }
    

Log in to reply
 

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