128. Longest Consecutive Sequence

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

For example,

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

public class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i : nums){
            set.add(i);
        }
        int max = 0;
        for(int val : nums){
            if(set.contains(val)){
                set.remove(val);
                int low = val -1;
                while(set.contains(low)){
                    set.remove(low);
                    low--;
                }
                int up = val + 1;
                while(set.contains(up)){
                    set.remove(up);
                    up++;
                }
                max = Math.max(max, (up - low - 1));
            }
        }

        return max;
    }
}

public class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i : nums){
            set.add(i);
        }
        int max = 0;
        for(int i=0; i< nums.length; i++){
            int low = nums[i] -1;
            while(set.contains(low)){
                set.remove(low);
                low--;
            }

            int up = nums[i] + 1;
            while(set.contains(up)){
                set.remove(up);
                up++;
            }
            max = Math.max(max, (up - low - 1));
        }

        return max;
    }
}