Weighted Quick Union Find Path Compression - Java


  • 0
    L

    public class Solution {

    public int numIslands(char[][] grid) {
        //Corner case
        if(grid == null || grid.length == 0) return 0;
        if(grid[0] == null || grid[0].length == 0) return 0;
        
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col; 
        
        QuickFindPathComp qfpc = new QuickFindPathComp(size, grid);
        
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == '1'){
                    int currIndex = i * col + j;
                    int upIndex = (i - 1) * col + j;
                    int downIndex = (i + 1) * col + j;
                    int leftIndex = i * col + (j - 1);
                    int rightIndex = i * col + (j + 1);
                    
                    //up
                    if(i > 0 && grid[i-1][j] == '1'){
                        qfpc.union(currIndex, upIndex);
                    }
                    
                    //down
                    if(i > row - 1 && grid[i+1][j] == '1'){
                        qfpc.union(currIndex, downIndex);
                    }
                    
                    //left
                    if(j > 0 && grid[i][j - 1] == '1'){
                        qfpc.union(currIndex, leftIndex);
                    }
                    
                    //right
                    if(j < col - 1 && grid[i][j + 1] == '1'){
                        qfpc.union(currIndex, rightIndex);
                    }
                }
            }
        }
        return qfpc.getCount();
    }
    

    }

    class QuickFindPathComp {
    private int[] id;
    private int[] sz;
    private int count;

    public QuickFindPathComp(int size, char[][] grid){
        id = new int[size];
        sz = new int[size];
        
        //Initialize
        for(int i = 0; i < size; i++){
            id[i] = i;
            sz[i] = 1; //each spot is an individual tree
        }
        
        //Counting how many spots are a land
        for(int row = 0; row < grid.length; row++){
            for(int col = 0; col < grid[0].length; col++){
                if(grid[row][col] == '1'){
                    count++;
                }
            }
        }
    }
    
    public int getCount(){
        return count;
    }
    
    public int root(int p){
        while(p != id[p]){
            id[p] = id[id[p]]; // for path compression
            p = id[p];
        }
        return p;
    }
    
    public void union(int p, int q){
        int pId = root(p); //find p's current parent root 
        int qId = root(q); //find q's current parent root
        
        //if p & q is connected then return 
        //Otherwise count - 1, because land p , q is connected with each others
        if (pId == qId){
            return;
        }
        count--; 
        
        // refactor the tree -> smaller tree should append into large tree
        if(sz[pId] < sz[qId]){
            id[pId] = id[qId]; 
            sz[qId] += sz[pId]; 
        }else{
            id[qId] = id[pId]; 
            sz[pId] += sz[qId]; 
        }
    }
    

    }


Log in to reply
 

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