Leetcode 128: Longest Consecutive Sequence

Problem:
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.

Analysis:

 The idea is to select one element first and then search larger consecutive ones and smaller ones. In this process, we need a map to record whether an integer exists or not and skip elements we have visited before.

Code:

public class Solution {
    public int longestConsecutive(int[] num) {
        Map<Integer,Boolean> map=new HashMap<Integer,Boolean>();
        for(int i=0;i<num.length;i++){
            map.put(num[i],true);
        }
        int maxLen=Integer.MIN_VALUE;
        for(int i=0;i<num.length;i++){
            if(map.get(num[i])){//not visited
                int val=num[i];
                int len=1;
                while(map.containsKey(--val)){
                    len++;
                    map.put(val,false);
                }
                val=num[i];
                while(map.containsKey(++val)){
                    len++;
                    map.put(val,false);
                }
                if(len>maxLen){
                    maxLen=len;
                }
            }
        }
        return maxLen;
    }
}