Java solution using Union Find


  • 1
    L
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int res = 1;
        Map<Integer,Integer> map = new HashMap<>();
        int count = 0;
        for(int num : nums){
           if(!map.containsKey(num)) map.put(num,count++);
        }
        UnionFind uf = new UnionFind(count);
        for(int num : nums){
            if(map.containsKey(num - 1)) uf.union(map.get(num),map.get(num - 1));
            if(map.containsKey(num + 1)) uf.union(map.get(num),map.get(num + 1));
            res = Math.max(res,uf.rank[uf.find(map.get(num))]);
        }
        return res;
    }
    private class UnionFind{
        int[] id;
        int[] rank;
        private UnionFind(int n){
            id = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++){
                id[i] = i;
                rank[i] = 1;
            }
        }
       public int find(int i){
           if(i != id[i]){
               id[i] = find(id[i]);
           }
           return id[i];
       }
       public void union(int i,int j){
           int ii = find(i);
           int jj = find(j);
           if(ii == jj) return;
           if(rank[ii] > rank[jj]){
               id[jj] = ii;
               rank[ii] += rank[jj];
           }
           else{
               id[ii] = jj;
               rank[jj] += rank[ii];
           }
       }
    }

Log in to reply
 

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