Java Solution for Longest Consecutive Sequence Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe solution utilizes a HashSet to efficiently check the presence of elements in the ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe solution utilizes a HashSet to efficiently check the presence of elements in the array. It iterates through the array twice: once to add all elements to the set, and again to find the longest consecutive subsequence for each element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Create a HashSet and add all elements from the array to the set.\n- Initialize a variable called max to keep track of the maximum length of consecutive subsequence found so far.\n- Iterate through the array and for each element e:\na. Check if e-1 is present in the set. If it is, it means e is not the starting element of a subsequence, so we continue to the next element.\nb. If e-1 is not present, we start counting the length of the consecutive subsequence. We increment count and remove e-1 from the set.\nc. Next, we check if e+1 is present in the set. If it is, we continue counting the length of the consecutive subsequence by incrementing count and removing e+1 from the set.\nd. We update the value of max by taking the maximum of the current count and max.\n- Return the value of max as the length of the longest consecutive subsequence.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of this solution is O(n), where n is the length of the input array. The initial iteration to add elements to the set takes O(n), and the subsequent iteration to find the consecutive subsequences also takes O(n). Since both iterations are performed independently, the overall time complexity is O(n + n) = O(n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity of this solution is O(n) as the HashSet is used to store the elements of the input array. In the worst-case scenario, where all elements are unique, the HashSet will store all n elements.\n\n# Code\n```\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        // if array is empty, return 0\n        if (nums.length == 0) \n        {\n            return 0;\n        }\n        Set<Integer> set = new HashSet<Integer>();\n        int max = 1;\n        for (int e : nums)\n            set.add(e);\n        for (int e : nums) \n        {\n            int left = e - 1;\n            int right = e + 1;\n            int count = 1;\n            while (set.contains(left)) \n            {\n                count++;\n                set.remove(left);\n                left--;\n            }\n            while (set.contains(right)) \n            {\n                count++;\n                set.remove(right);\n                right++;\n            }\n            max = Math.max(count, max);\n        }\n        return max;\n    }\n}\n```
['Java']