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! ^_^

view plainprint?

1. public class Solution {  
2.     public int longestConsecutive(int[] nums) {  
3.         int maxLength = 0;  
4.         Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();  
5.         Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();  
6.         Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();  
7.         int left, right, l;  
8.         for(int i = 0; i < nums.length; i++){  
9.             if(visited.containsKey(nums[i])) continue;  
10.             visited.put(nums[i], true);  
11.             left = right = nums[i];  
12.             if(map1.containsKey(nums[i]-1))   
13.                 left -= map1.get(nums[i]-1);  
14.             if(map2.containsKey(nums[i] + 1))  
15.                 right += map2.get(nums[i]+1);  
16.             l = right - left + 1;  
17.             if(maxLength < l) maxLength = l;  
18.               
19.             map1.put(right, l);  
20.             map2.put(left, l);  
21.         }  
22.         return maxLength;  
23.     }  
24. }  

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.

view plainprint?

1. public class Solution {  
2.     public int longestConsecutive(int[] num) {  
3.         int longest = 0;  
4.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
5.         for(int i = 0;i < num.length;i++){  
6.             // if there is no duplicates, these two lines can be commented  
7.             if(map.containsKey(num[i])) continue;  
8.             map.put(num[i],1);  
9.   
10.             int end = num[i];  
11.             int begin = num[i];  
12.             if(map.containsKey(num[i]+1))  
13.                 end = num[i] + map.get(num[i]+1);  
14.             if(map.containsKey(num[i]-1))  
15.                 begin = num[i] - map.get(num[i]-1);  
16.             longest = Math.max(longest, end-begin+1);  
17.             map.put(end, end-begin+1);  
18.             map.put(begin, end-begin+1);  
19.         }  
20.         return longest;  
21.     }  
22. }  

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:

view plainprint?

1. public class Solution {  
2.     public int longestConsecutive(int[] num) {  
3.         int res = 0;  
4.         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
5.         for (int n : num) {  
6.             if (!map.containsKey(n)) {  
7.                 int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;  
8.                 int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;  
9.                 // sum: length of the sequence n is in  
10.                 int sum = left + right + 1;  
11.                 map.put(n, sum);  
12.       
13.                 // keep track of the max length   
14.                 res = Math.max(res, sum);  
15.       
16.                 // extend the length to the boundary(s)  
17.                 // of the sequence  
18.                 // will do nothing if n has no neighbors  
19.                 map.put(n - left, sum);  
20.                 map.put(n + right, sum);  
21.             }  
22.             else {  
23.                 // duplicates  
24.                 continue;  
25.             }  
26.         }  
27.         return res;  
28.     }  
29. }  

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

view plainprint?

1. public class Solution {  
2.     public int longestConsecutive(int[] num) {  
3.         int longest = 0;  
4.         Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
5.         for(int i = 0; i< num.length; i++){  
6.             map.put(num[i], false);  
7.         }  
8.           
9.         int l, k;  
10.         for(int i = 0;i < num.length;i++){  
11.               
12.             if(map.containsKey(num[i]-1) || map.get(num[i])) continue;  
13.             map.put(num[i], true);  
14.             l = 0; k = num[i];  
15.             while (map.containsKey(k)){  
16.                 l++;  
17.                 k++;  
18.             }  
19.             if(longest < l) longest = l;  
20.               
21.         }  
22.         return longest;  
23.     }  
24. }  

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;
    }
}