class Solution {
    /**
    1. Store all elements in a HashSet, This allows O(1) lookup for checking if a number exists.
    2. Only start building a sequence from numbers that are the beginning 
        - number is the start if, set does not contains (element-1)
        - count (currentLength) how long the sequence goes, so Expand forward (ele + 1, ele + 2, …)
        - once you found the current length of sequence, Track the maximum length
    3. repeat step-2 for all the array elements
    4. return the max length
    */
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0)
            return 0;
        
        // to remove duplicates
        HashSet<Integer> set = new HashSet<>();
        for(int ele : nums)
            set.add(ele);

        int maxLength = 0;
        for(int ele : nums)
        {
            // find the start of sequence
            if(set.contains(ele - 1) == false) // this is not the start
            {
                int length = 1;
                while(set.contains(ele + 1))
                {
                    ele++;
                    length++;
                }
                maxLength = Math.max(length, maxLength);
            }
        }
        return maxLength;
    }
}