My simple Union-Find solution


  • 12
    H

    The basic idea is the Union-Find approach. We assign a root number for each island, and use an array to record this number. For each input, we check its four neighbor cells. If the neighbor cell is an island, then we retrieve the root number of this island. If two neighbor cells belong to two different islands, then we union them and therefore the total number of islands will become one less.

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        //use an array to hold root number of each island
    	int[] roots = new int[m*n];
        //initialize the array with -1, so we know non negative number is a root number
        Arrays.fill(roots, -1);
        
        int[] xOffset ={0, 0, 1, -1};
        int[] yOffset = {1, -1, 0, 0};
        
        List<Integer> result = new ArrayList<Integer>();
        
        for(int[] position : positions){
        	//for each input cell, its initial root number is itself
            roots[position[0]*n + position[1]] = position[0]*n + position[1];
            //count variable is used to count the island in current matrix.
            //firstly, we assume current input is an isolated island
            int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
            //check neighbor cells
            for(int i = 0; i < 4; i++){
                int newX = xOffset[i] + position[0];
                int newY = yOffset[i] + position[1];
                //if we found one neighbor is a part of island
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
                	//get the root number of this island
                    int root1 = find(newX * n + newY, roots);
                    //get the root number of input island
                    int root2 = roots[position[0]*n + position[1]];
                    //if root1 and root2 are different, then we can connect two isolated island together,
                    // so the num of island - 1
                    if(root1 != root2) count--;
                    //update root number accordingly
                    roots[root1] = root2;
                }
            }
            result.add(count); 
        }
        
        return result;
    }
    
    public int find(int target, int[] roots){
    	//found root
        if(roots[target] == target) return target;
        //searching for root and update the cell accordingly
        roots[target] = find(roots[target], roots);
        //return root number
        return roots[target];
    }

  • 1

    I think this line

    int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
    

    can be replace with count++; if you move the initialization outside before the loop like this int count = 0;


  • 0
    Z

    My c++ version got LTE ; (


  • 2

    This explanation is pretty easy to understand. Thanks!

    One little improvements could be to put int root2 = roots[position[0]*n + position[1]]; before checking each neighbor cell:

    //check neighbor cells
            for (int i = 0; i < 4; i++) {
    

    like

        for (int[] position : positions) {
                //for each input cell, its initial root number is itself
                int inputRoot = roots[position[0] * n + position[1]] = position[0] * n + position[1];
                //cnt variable is used to cnt the island in current matrix.
                //firstly, we assume current input is an isolated island
                int cnt = result.isEmpty() ? 1 : result.get(result.size() - 1) + 1;
                //check neighbor cells
                
                for (int i = 0; i < 4; i++){
                    int newX = xOffset[i] + position[0];
                    int newY = yOffset[i] + position[1];
                    //if we found one neighbor is a part of island
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1) {
                        //get the root number of this island
                        int rootOfNeighbor = find(newX * n + newY, roots);
                        //if rootOfNeighbor and inputRoot are different, then we can connect two isolated island together,
                        // so the num of island - 1
                        if (rootOfNeighbor != inputRoot) cnt--;
                        //update root number accordingly
                        roots[rootOfNeighbor] = inputRoot;
                    }
                }
                result.add(cnt);      
        }
    

    instead of

        for (int[] position : positions) {
                //for each input cell, its initial root number is itself
                roots[position[0]*n + position[1]] = position[0]*n + position[1];
                //count variable is used to count the island in current matrix.
                //firstly, we assume current input is an isolated island
                int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
                //check neighbor cells
                for(int i = 0; i < 4; i++){
                    int newX = xOffset[i] + position[0];
                    int newY = yOffset[i] + position[1];
                    //if we found one neighbor is a part of island
                    if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
                        //get the root number of this island
                        int root1 = find(newX * n + newY, roots);
                        //get the root number of input island
                        int root2 = roots[position[0]*n + position[1]];
                        //if root1 and root2 are different, then we can connect two isolated island together,
                        // so the num of island - 1
                        if(root1 != root2) count--;
                        //update root number accordingly
                        roots[root1] = root2;
                    }
                }
                result.add(count); 
        }
    

    Since we only need to assign the root of the input island once when iterating over its four neighbor cells.


  • 0

    Another improvement could be to replace

    roots[target] = find(roots[target], roots);
    //return root number
    return roots[target];
    

    with

    return find(roots[target], roots);
    

    in find() method


  • 0
    Z
    This post is deleted!

  • 0
    Z

    @BryanBo.Cao The original way is intended, which set all the nodes along the path to directly point to the root. It makes the tree flat, known as path compression.


Log in to reply
 

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