Share my Java code beating 84%. Using UnionFind, 2D->1D trick.


  • 0
    V

    use a counter to track the island.
    every time put a 1 in the board, counter increase by one
    every time when merging two island, counter decrease by one

    running time: O(k)
    union and find are const operations
    time complexity: O(MN)

    public class Solution {
        private int[] p;
        private int n;
        private int count = 0;
        
        private int find(int n){
            if(p[n] != n)
                p[n] = find(p[n]);
            return p[n];
        }
        private void union(int a, int b){
            if(!isInSameSet(a, b)){
                p[find(a)] = p[find(b)];
                count --;
            }
        }
        private boolean isInSameSet(int a, int b){
            return find(a) == find(b);
        }
        
        private int getLoc(int row, int col){
            return row * n + col;
        }
        
        public List<Integer> numIslands2(int m, int n, int[][] pos) {
            this.n = n;
            p = new int[m * n];
            for(int i = 0; i < p.length; i++)
                p[i] = i;
            
            int[][] b = new int[m][n];
            
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < pos.length; i++){
                int row = pos[i][0], col = pos[i][1];
                b[row][col] = 1;
                count ++;
                if(row - 1 >= 0 && b[row - 1][col] == 1)
                    union(getLoc(row, col), getLoc(row - 1, col));
                if(row + 1 < m && b[row + 1][col] == 1)
                    union(getLoc(row, col), getLoc(row + 1, col));
                if(col - 1 >= 0 && b[row][col - 1] == 1)
                    union(getLoc(row, col), getLoc(row, col - 1));
                if(col + 1 < n && b[row][col + 1] == 1)
                    union(getLoc(row, col), getLoc(row, col + 1));
                res.add(count);
            }
            
    
            return res;
            
        }
    }

Log in to reply
 

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