128. Longest Consecutive Sequence Leetcode Java

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:

Intuitive solution: Sort the the array, and check all consecutive sequences and find the longest. Time complexity:O(nlogn)

Advance solution 1: consider it as intervals, eg. let's use the example given in the problem, [100](interval with size 1); [4]; [200]; [1]; when we process 3, we find that, it is mergeable with[4], [3,4]; after that when we process 2, we find that it can be merged with both [1], [3,4] => [1,2,3,4], so I use a hashmap to store the intervals information: start/end with the length, for each processing integer, check if the map contains its consecutive numbers if yes, then this number can be merged with stored intervals. Then update the stored intervals accordingly. 

Time complexity: O(n). O(n) extra space 

 public int longestConsecutive(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int res=1;  
    HashMap<Integer, Integer> map=new HashMap<Integer,Integer>();  
    for(int i=0;i<num.length;i++){  
      if(map.containsKey(num[i])) continue;  
      if(map.containsKey(num[i]-1) && map.containsKey(num[i]+1)){  
        int start=num[i]-map.get(num[i]-1);  
        int end=num[i]+map.get(num[i]+1);  
        map.put(start,end-start+1);  
        map.put(end,end-start+1);  
        map.put(num[i],1);  
        res=Math.max(res,end-start+1);  
      }  
      else if(map.containsKey(num[i]-1)){  
        int start=num[i]-map.get(num[i]-1);  
        map.put(start,num[i]-start+1);  
        map.put(num[i],num[i]-start+1);  
        res=Math.max(res,num[i]-start+1);  
      }  
      else if(map.containsKey(num[i]+1)){  
        int end=num[i]+map.get(num[i]+1);  
        map.put(end,end-num[i]+1);  
        map.put(num[i],end-num[i]+1);  
        res=Math.max(res,end-num[i]+1);  
      }  
      else map.put(num[i],1);  
    }  
    return res;  
   }  

Advance solution 2:
Use a hashset to store all the integers, determine the upper boundary and lower boundary by checking if the hashset contains the consecutive numbers one by one. If yes, remove the number in the hashset. So the total time will be O(2*n)=O(n). O(n) extra space

  public int longestConsecutive(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int res=1;  
    HashSet<Integer> helper=new HashSet<Integer>();  
    for(int i=0;i<num.length;i++){  
      helper.add(num[i]);  
    }  
    for(int i=0;i<num.length;i++){  
      if(!helper.contains(num[i])) continue;  
      int temp=num[i];  
      int r=1;  
      while(helper.contains(temp+r)){  
        helper.remove(temp+r);  
        r++;  
      }  
      int l=1;  
      while(helper.contains(temp-l)){  
        helper.remove(temp-l);  
        l++;  
      }  
      res=Math.max(l+r-1,res);  
    }  
    return res;  
   }