O(K+N) Java solution, clean, using optimized DSU (path compression and union by rank heuristics)


  • 0
    J
    public class Solution {
        
        static class DSU{
        	int[] parent;
        	int[] rank;
        	int[] size; // size of each set, or more accurately size of set which contains the i'th node
        	int setCount; // total number of distinct sets
        
        	// using zero based indexing
        	public DSU(int n){
        		parent = new int[n];
        		rank = new int[n];
        		size = new int[n];
        		setCount = n;
        
        		for(int i=0; i<n; i++){
        			makeSet(i);
        		}
        	}
        
        	public void makeSet(int x){
        		parent[x] = x;
        		rank[x] = x;
        	}
            
            public boolean union(int x, int y){
                int px = findSet(x), py = findSet(y);
                if(px == py) return false;
                link(px, py);
                return true;
            }
            
        	private void link(int x, int y){
        		if(rank[x] > rank[y]) parent[y] = x;
        		else{
        			parent[x] = y;
        			if(rank[x] == rank[y]) rank[y]++;
        		}
        	}
        
        	public int findSet(int x){
        		if(parent[x]!=x) parent[x] = findSet(parent[x]);
        		return parent[x];
        	}
        }
        
        // returns the vertice mapping for position i,j, using 0 based indexing
        int v_num(int i, int j){
            return i*n + j;
        }
        
        // clockwise from 12:00
        int[] dx = new int[]{0,1,0,-1};
        int[] dy = new int[]{-1,0,1,0};
        
        int[][] grid;
        int m, n;
        
        public List<Integer> numIslands2(int m_, int n_, int[][] positions) {
            m = m_; 
            n = n_;
            grid = new int[m][n];
            DSU dsu = new DSU(m*n);
            List<Integer> res = new ArrayList<>();
            
            int cnt = 0, lcl = 0;
            for(int i=0; i<positions.length; i++){
                cnt++; // assuming each position is an actual piece of water not already land
                lcl = 0;
                
                int py = positions[i][0];
                int px = positions[i][1];
                grid[py][px] = 1;
                
                for(int j=0; j<4; j++){
                    int x = px+dx[j], y = py+dy[j];
                    
                    if(x<0 || x>=n || y<0 || y>=m) continue;
                    
                    if(grid[y][x] == 1){
                        int u = v_num(py, px); 
                        int w = v_num(y, x);
                        if(dsu.union(u, w)) lcl++;
                    }
                }
                cnt-=lcl;
                res.add(cnt);
            }
            return res;
        }
    }

Log in to reply
 

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