128. Longest Consecutive Sequence

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.

Solution

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

        int maxValue = 0;
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if (!set.contains(cur - 1)) {

                int temp = cur + 1;
                while (set.contains(temp)) {
                    temp++;
                }

                maxValue = maxValue > (temp - cur) ? maxValue : temp - cur;
            }
        }

        return maxValue;
    }
}