Leetcode 128 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 1: The difficulty is the O(n) complexity. Maintain the two ends of the consecutive elements use HashMap. For [1,2,3,4], the two end is 1 & 4. when check 1, it should know most right is 4 and left is itself 1; when check 4, it should know most left is 1 and right is 4. keep updating max value which is 4-1+1=4 in this case.

 public class Solution {  
   public int longestConsecutive(int[] nums) {  
     Map<Integer,Integer> left=new HashMap<>();  
     Map<Integer,Integer> right=new HashMap<>();  
     int res=0;  
     for (int i: nums) {  
       if (left.containsKey(i)) continue;  
       else {  
         left.put(i,i);  
         right.put(i,i);  
         int l=i, r=i;  
         if (left.containsKey(i-1)) l=left.get(i-1);  
         if (right.containsKey(i+1)) r=right.get(i+1);  
         right.put(l,r);  
         left.put(r,l);  
         res=Math.max(res,r-l+1);  
       }  
     }  
     return res;  
   }  
 }