Java O(N) Union Set Find
We use a hash map to  keep track of each elements\' index in the nums array. For an element e, first we check if this element has already been seen before. If y
We use a hash map to  keep track of each elements\' index in the *nums* array. For an element *e*, first we check if this element has already been seen before. If yes, ignore it. If element has not been seen before,  we add it\'s index to the map. We then perform union of *e* with elements *e-1* and *e+1*, if these elements have been seen before in the array. (I modified the union function to return the size of the new set. We could also have just used a global size variable.)\n```\nclass UnionSet{\n    int[] parents;\n    int[] sizes;\n    int[] ranks;\n    UnionSet(int n){\n        parents = new int[n];\n        ranks = new int[n];\n        sizes = new int[n];\n        for(int i=0;i<n;i++){\n            parents[i] = i;\n        }\n        Arrays.fill(sizes, 1);\n    }\n    \n    public int union(int a, int b){\n        // union by rank heuristic\n        int idxA = findSet(a);\n        int idxB = findSet(b);\n\t\tif(idxA == idxB)\n\t\t    return -1;\n\t\t\t\n        if(ranks[idxA]>ranks[idxB]){\n            parents[idxB] = idxA;\n            sizes[idxA] += sizes[idxB];\n            return sizes[idxA];\n        } else {\n            parents[idxA] = idxB;\n            sizes[idxB] += sizes[idxA];\n            if(ranks[idxB]==ranks[idxA]){\n                ranks[idxB]++;\n            }\n            return sizes[idxB];\n        }\n    }\n    \n    public int findSet(int idx){\n        // path compression heuristic\n        if(parents[idx]!=idx)\n            parents[idx] = findSet(parents[idx]);\n        return parents[idx];\n    }\n}\n\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        int n = nums.length;\n        if(n<=1){\n            return n;\n        }\n        int longestConsecutiveSeqLen = 1;\n\t\t\n        // to track index of each element in array\n        Map<Integer, Integer> mp = new HashMap<>(); \n        UnionSet unionSet = new UnionSet(n);\n        for(int i=0;i<n;i++){\n            int e = nums[i];\n            if(mp.containsKey(e)){\n                continue;\n            }\n            mp.put(e, i);\n            if(mp.containsKey(e-1)){\n                longestConsecutiveSeqLen = Math.max(longestConsecutiveSeqLen, unionSet.union(i, mp.get(e-1)));\n            }\n            \n            if(mp.containsKey(e+1)){\n                longestConsecutiveSeqLen = Math.max(longestConsecutiveSeqLen, unionSet.union(i, mp.get(e+1)));\n            }\n            \n        }\n        return longestConsecutiveSeqLen;\n    }\n}\n```
[]