JAVA, union find method, clean code with detailed comments


  • 0
    public class Solution {
        /*
         * Idea : Union Find
         * If the new island does not connect any other existing islands, total islands increase 1
         * If the new island connects x "different" islands together, total islands increase (i - x)
         *
         * Key: "different" root of an island differentiate it from other islands
         * 
         * real performance: 15ms
         * who can help me to calculate the time complexity? Thanks.
         */
        private int[] array;
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> result = new ArrayList<>();
            int len = m * n;
            array = new int[len];
            for (int i = 0; i < len; i ++) array[i] = i;
            int[][] island = new int[m][n];
            int num_island = 0;
            for (int[] position : positions) {
                int x = position[0];
                int y = position[1];
                int index = x * n + y;
                int connect = 0;
                int pos2 = x * n + y;
                island[x][y] = 1;
                if (x > 0 && island[x - 1][y] == 1) {
                    connect += helper(pos2 - n, pos2);
                }
                if (x < m - 1 && island[x + 1][y] == 1) {
                    connect += helper(pos2 + n, pos2);
                }
                if (y > 0 && island[x][y - 1] == 1) {
                    connect += helper(pos2 - 1, pos2);
                }
                if (y < n - 1 && island[x][y + 1] == 1) {
                    connect += helper(pos2 + 1, pos2);
                }
                num_island +=  1 - connect;
                result.add(num_island);
            }
            return result;
        }
    
        public int helper(int pos1, int pos2) {
            int root = findRoot(pos1);
            array[root] = pos2;
            return root != pos2 ? 1 : 0;
        }
    
        public int findRoot(int pos) {
            if (pos == array[pos]) {
                return pos; 
            } else {
                array[pos] = findRoot(array[pos]);
                return array[pos];
            }
        }
    }
    

Log in to reply
 

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