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:
Save sequence length on its borders.
Since when we add an new element into the LCS, we either operate on the left most or the right most, so there is no need to update sequence length of other elements.

public class Solution {
    public int longestConsecutive(int[] num) {
        HashMap hash = new HashMap(); 
        if(num.length == 0) return 0;
        int maxLength = 1;
        for(int cur : num){
            if(!hash.containsKey(cur)){
                int seqLength = 1;
                int leftBorder = 0;
                int rightBorder = 0;
                hash.put(cur, seqLength);
                if(hash.containsKey(cur-1)){
                    leftBorder = (cur-1) - hash.get(cur-1) + 1;
                    seqLength = cur - leftBorder + 1;
                    hash.put(leftBorder, seqLength);
                    hash.put(cur, seqLength);
                    if(seqLength > maxLength) maxLength = seqLength;
                }
                if(hash.containsKey(cur+1)){
                    leftBorder = cur - hash.get(cur) + 1;
                    rightBorder = cur+1 + hash.get(cur+1) -1;
                    seqLength = rightBorder - leftBorder + 1;
                    hash.put(leftBorder, seqLength);
                    hash.put(rightBorder, seqLength);
                    if(seqLength > maxLength) maxLength = seqLength;
                }
            }
        }
        return maxLength;
    }
}

The first solution is confusing, so let's check out the second one.

public class Solution {
    public int longestConsecutive(int[] num) {
        HashSet set = new HashSet();
        int result = 0;
        for(int e : num){
            set.add(e);
        }
        for(int e : num){
            int count = 1;
            int left = e - 1;
            int right = e + 1;
            
            while(set.contains(left)){
                count++;
                set.remove(left);   // !!!!!!!!!!!!!!!  otherwise complexity would be O(mn)
                left--;
            }
            
            while(set.contains(right)){
                count++;
                set.remove(right);
                right++;
            }
            
            result = Math.max(count, result);
        }
        return result;
    }
}