Longest Consecutive Sequence

Source

• lintcode: Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the
longest consecutive elements sequence.

Example
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Clarification
Your algorithm should run in O(n) complexity.

Java

public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        int maxLen=0;
        for(int n: nums){
            map.put(n, false);
        }
        for(int n : nums){
            if(!map.get(n)){
                map.put(n, true);
                int len  = lookup(map, n, 1) + lookup(map, n, -1)+1;
                maxLen=Math.max(maxLen, len);
            }
        }
        return maxLen;
    }

    public int lookup(HashMap<Integer, Boolean> map, int num, int shift){
        int len=0;
        int n = num+shift;
        while(map.containsKey(n) && !map.get(n)){
            len++;
            map.put(n, true);
            n+=shift;
        }
        return len;
    }
}