java solution beat 95% using UnionFind


  • 0
    C

    public class Solution {

    class UnionFind {
        private int [] sz;
        private int [] id;
        //private int count;
        private int maxsz = 1;
        
        public UnionFind(int n) {
            //count = n;
            id = new int[n];
            for(int i = 0; i < n; i++) {
                id[i] = i;
            }
            sz = new int[n];
            for(int i = 0; i < n; i++) {
                sz[i] = 1;
            }
            
        }
        
        public void union(int p, int q) {
            int root1 = find(p);
            int root2 = find(q);
            if(root1 == root2) return;
            if(sz[root1] < sz[root2]){
                id[root1] = root2;
                sz[root2] += sz[root1];
                if( sz[root2] > maxsz) maxsz = sz[root2];
            }
            else{
                id[root2] = root1;
                sz[root1] += sz[root2];
                if( sz[root1] > maxsz) maxsz = sz[root1];
            }
            //count--;
        }
        
        public int find(int p) {
            while(id[p] != p) p = id[p];
            return p;
        }
        
        public int maxsz(){
            return maxsz;
        }
    }
    
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        if(n == 0) return 0;
        UnionFind uf = new UnionFind(n);
        for(int i = 0;i < n-1; ) {
            int j = i + 1;
            while(nums[i] == nums[j]){
                j++;
                if(j == n) return uf.maxsz;
            } 
            if(nums[i] - nums[j] == 1 || nums[i] - nums[j] == -1) uf.union(i,j);
            i = j;
        }
        return uf.maxsz;
    }
    

    }


Log in to reply
 

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