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.

Another problem can be solved by hash map! I remember one of my SWE friend posted on FB about hash map: "It's incredibly fast!"

Well, I haven't reached to that state. But using hash map does have lots of convenience.

This problem, we use a HashMap <Integer, Integer> to track if the number in the array has been counted in one of the sequences. The key is the element, the value is either 0 (not in any sequence) and 1 (already in a sequence).

We search the map to get the sequence for a particular element, and compare to the longest sequence so far.

public class LongestSequence {
    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0)
            return 0;
        HashMap hm = new HashMap();
        for (int i : num)
            hm.put(i, 0);
        int max = 1;
        for (int i : num)
        {
            //already checked as part of a sequence
            if (hm.get(i) == 1)
                continue;
            int tmp = i;
            int currmax = 1;
            while(hm.containsKey(tmp+1))
            {
                currmax++;
                hm.put(tmp, 1);
                tmp++;
            }
            tmp = i;
            while (hm.containsKey(tmp-1))
            {
                currmax++;
                hm.put(tmp,1);
                tmp--;
            }
            max = Math.max(max, currmax);
        }

        return max;
        
    }
}