Java || Union Find || HashMap || O(n) Time Complexity
Pre-requisite Disjoint Set Data Structure or Union Find Algorithm. You can learn it here\nTo solve this problem in O(n) TC, where n is number of elements in the
**Pre-requisite** Disjoint Set Data Structure or Union Find Algorithm. You can learn it [here](https://www.coursera.org/learn/algorithms-part1/home/week/1)\nTo solve this problem in O(n) TC, where n is number of elements in the array, we can use the Union Find Algorithm.\n1.  Create a DisjointSet using two hashmaps, **id** and **size**.\n2.  Iterate through the array and if **nums[i]** is not present in **id**, then firstly add it into the **id** map and then:\n\t\t a) If **(nums[i] - 1)** is present in **id**, perform **union(nums[i], nums[i-1])**\n\t\t b) If **(nums[i] + 1)** is present in **id**, perform **union(nums[i], nums[i+1])**\n3. Initialize a variable **longest** = 0.\n4. Iterate through the **size** map, and update **longest** with the maximum value present in the **size** map. \n\nSince, the complexity for **find** method is constant (using Path Compression and weighted union techniques), the algorithm runs in O(n) time complexity.\n\n```\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        DisjointSet ds = new DisjointSet();\n        \n        for(int i = 0; i < nums.length; i++){\n            if(!ds.id.containsKey(nums[i])){\n                ds.id.put(nums[i], nums[i]);\n                ds.size.put(nums[i], 1);\n                \n                if(ds.id.containsKey(nums[i] + 1)) ds.union(nums[i], nums[i] + 1);\n                if(ds.id.containsKey(nums[i] - 1)) ds.union(nums[i], nums[i] - 1);\n            }\n        }\n        \n        int longest = 0;\n        \n        for(Map.Entry<Integer, Integer> entry : ds.size.entrySet()){\n            longest = Math.max(longest, entry.getValue());\n        }\n        \n        return longest;\n    }\n}\n\nclass DisjointSet{\n    HashMap<Integer, Integer> id, size;\n    \n    public DisjointSet(){\n        this.id = new HashMap<>();\n        this.size = new HashMap<>();\n    }\n    \n    public int find(int n){\n        if(id.get(n) == n) return n;\n        id.put(n, find(id.get(n)));\n        return id.get(n);\n    }\n    \n    public void union(int u, int v){\n        int idU = find(u);\n        int idV = find(v);\n        if(idU == idV) return;\n        if(size.get(idU) < size.get(idV)){\n            id.put(idU, idV);\n            size.put(idV, size.get(idU) + size.get(idV));\n        } else {\n            id.put(idV, idU);\n            size.put(idU, size.get(idU) + size.get(idV));\n        }\n    }\n}\n```
['Hash Table', 'Union Find', 'Java']