Longest Consecutive Sequence: Some different approaches.

Problem Description

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.

Solutions
I. Intuitive Solution

For each element e we check that if e is visited . If not, we check the length of the sequence ends at e-1, and length of the sequence starts at e+1, then combine these 2 sequence. (Note that we only update the 2 ends of the sequence). The following solution using 3 HashMap !!! To see why the "visited" HashMap needed, you can check on the following test case:
[-6,8,-5,7,-9,-1,-7,-6,-9,-7,5,7,-1,-8,-8,-2,0]
Take your time! ^_^

public class Solution {
    public int longestConsecutive(int[] nums) {
        int maxLength = 0;
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();
        int left, right, l;
        for(int i = 0; i < nums.length; i++){
            if(visited.containsKey(nums[i])) continue;
            visited.put(nums[i], true);
            left = right = nums[i];
            if(map1.containsKey(nums[i]-1)) 
                left -= map1.get(nums[i]-1);
            if(map2.containsKey(nums[i] + 1))
                right += map2.get(nums[i]+1);
            l = right - left + 1;
            if(maxLength < l) maxLength = l;
            
            map1.put(right, l);
            map2.put(left, l);
        }
        return maxLength;
    }
}

II. Improvement on the code

With the above code, we can reduce the space to only 1 HashMap.

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < num.length;i++){
            // if there is no duplicates, these two lines can be commented
            if(map.containsKey(num[i])) continue;
            map.put(num[i],1);

            int end = num[i];
            int begin = num[i];
            if(map.containsKey(num[i]+1))
                end = num[i] + map.get(num[i]+1);
            if(map.containsKey(num[i]-1))
                begin = num[i] - map.get(num[i]-1);
            longest = Math.max(longest, end-begin+1);
            map.put(end, end-begin+1);
            map.put(begin, end-begin+1);
        }
        return longest;
    }
}

III. The same idea as the II) approach can be expressed as the following code:

public class Solution {
    public int longestConsecutive(int[] num) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : num) {
            if (!map.containsKey(n)) {
                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
                // sum: length of the sequence n is in
                int sum = left + right + 1;
                map.put(n, sum);
    
                // keep track of the max length 
                res = Math.max(res, sum);
    
                // extend the length to the boundary(s)
                // of the sequence
                // will do nothing if n has no neighbors
                map.put(n - left, sum);
                map.put(n + right, sum);
            }
            else {
                // duplicates
                continue;
            }
        }
        return res;
    }
}

IV. Better solution

public class Solution {
    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i< num.length; i++){
            map.put(num[i], false);
        }
        
        int l, k;
        for(int i = 0;i < num.length;i++){
            
            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
            map.put(num[i], true);
            l = 0; k = num[i];
            while (map.containsKey(k)){
                l++;
                k++;
            }
            if(longest < l) longest = l;
            
        }
        return longest;
    }
}