O(n) in array

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i: nums) set.add(i);
        int maxStreak = 0;

        for(int i: nums){
            int  curStreak = 1;
            if(!set.contains(i-1)) {
                int j = i+1;
                while(set.contains(j)) {
                    curStreak ++;
                    j ++;
                }
                maxStreak = Math.max(curStreak, maxStreak);
            }
        }
        return maxStreak;
    }
}