// Longest Consecutive Sequence - https://leetcode.com/problems/longest-consecutive-sequence/description/

class Solution {

    // Sorting
    // Time Complexity: O(nlogn)
    // Space Complexity: O(1)
    // public int longestConsecutive(int[] nums) {

    //     if(nums.length == 0) {
    //         return 0;
    //     }

    //     int maxCount = 1;
    //     Arrays.sort(nums);

    //     for(int i = 0; i < nums.length - 1; i++) {
    //         int count = 1;
    //         while(i < nums.length - 1
    //             && (nums[i] + 1 == nums[i + 1]
    //                 || nums[i] == nums[i + 1])) {
                

    //             if ( i < nums.length - 1 && nums[i] == nums[i + 1]) {
    //                 i++;
    //                 continue;
    //             }

    //             count++;
    //             i++;
    //         }

    //         if (count > maxCount) {
    //             maxCount = count;
    //         }
    //     }

    //     return maxCount;
    // }

    // HashSet
    // Time Complexity: O(n)
    // Space Complexity: O(n)
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }

        Set<Integer> set = new HashSet<>();

        for(int num: nums) {
            set.add(num);
        }

        int maxCount = 1;
        for(int num: set) {
            if(!set.contains(num - 1)) {
                int count = 1;
                while(set.contains(num + count)) {
                    count++;
                }

                maxCount = Math.max(count, maxCount);
            }
            
        }

        return maxCount;
    }
}