Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

0 <= nums.length <= 105
-109 <= nums[i] <= 109

We would like to find the consecutive sequence for this we can actually sort the array and then track the array by looking if the next consecutive element is present in the list.

Sorting will take n log n complexity. So Let us think of solution that does not involve sorting.

We can use a HashSet to store the elements and compare with the current element and track the longest sequence

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int num:nums){
            set.add(num);
        }
        int longest = 0;
        for(int num:set){
            if(!set.contains(num-1)){
                int length =1;
                while(set.contains(num+length)){
                    length++;
                }
                longest = Math.max(longest,length);
            }
        }
        return longest;
    }
}

Time Complexity - O(N)

Space Complexity - O(N)