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) {
        if(nums == null || nums.length == 0) return 0;
        Map<Integer, Integer> start = new HashMap<Integer, Integer>();
        Map<Integer, Integer> end   = new HashMap<Integer, Integer>();
        int maxLen = 0;
        for(int num: nums) {
            if(!start.containsKey(num)) {
                start.put(num, num);
                end.put(num, num);

                Integer left = end.getOrDefault(num-1, num);
                Integer right = start.getOrDefault(num+1, num);

                start.put(left, right);
                end.put(right, left);
                maxLen = Integer.max(maxLen, right - left + 1);
            }
        }
        return maxLen;
    }
}