[Leetcode] 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.

The naive method is to sort the array, however, this would not meet the requirement of O(n) time complexity. So, I use a HashMap to hold each element and the max length from this element to the ones smaller than it. Assume that we have arrived at i, and we found A[i]-1 is visited and has a record, thus we don't need to check all the element one by one, we just add A[i]-1's record to one and this would be the longest possible consecutive sequence from A[i]. The total access of each record should not more than 2N. So we could meet the time complexity.

    public int longestConsecutive(int[] num) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = num.length;
        for(int i = 0; i < n; i++)
            if(map.containsKey(num[i]) == false)
                map.put(num[i], 0);
        for(int i = 0; i < n; i++)
            if(map.get(num[i]) == 0)
                dfs(num[i], map);
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            result = Math.max(result, map.get(num[i]));
        }
        return result;
    }
    
    private int dfs(int num, HashMap<Integer, Integer> map) {
        if(map.get(num) != 0)
            return map.get(num);
        if(map.containsKey(num-1) == true) {
            map.put(num, dfs(num-1, map) + 1);
        }
        else
            map.put(num, 1);
        return map.get(num);
    }

Another way is to expand a element to its right and left, like finding a connective component, and since connective component has some property as a set, we do not need to check other element in the same component, thus remove them from the set. In such a way, each element is at most visited once and all the operation needed is O(1), thus we could guarantee the time complexity to be O(n).

    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < num.length; i++)
            set.add(num[i]);
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < num.length; i++) {
            int left = num[i] - 1;
            int right = num[i] + 1;
            int count = 1;
            while(set.contains(left) == true) {
                count++;
                set.remove(left);
                left--;
            }
            while(set.contains(right) == true) {
                count++;
                set.remove(right);
                right++;
            }
            result = Math.max(result, count);
        }
        return result;
    }