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.

Analysis:
The question asks for finding the length of the longest consecutive elements sequence. Note that the array is unsorted and the question asks for the complexity in O(n). So we cannot sort the array first as sorting will take O(nlogn) time.

Solution:
A solution is to use Java HashSet, which is implemented as Hash Table, but cannot contains duplicated keys. We can first add all array elements into the set. Then for each array element, we check if it contains left and right consecutive elements.  

public class Solution {
    public int longestConsecutive(int[] num) {
        // if array is empty or contains 1 eleme
        if (num.length == 0 || num.length == 1) return num.length;
        
        HashSet<Integer> set = new HashSet<Integer>();
        int max = 1;
        
        // add array elements into the hash set
        for (int i : num)
            set.add(i);
        
        // For each array element, check consecutive sequence
        for (int i : num) {
            int left = i - 1;
            int right = i + 1;
            int count = 1;
            
            // check left consecutive sequence
            while (set.contains(left)) {
                count++;
                set.remove(left);
                left--;
            }
            
            // check right consecutive sequence
            while (set.contains(right)) {
                count++;
                set.remove(right);
                right++;
            }
            
            max = Math.max(count, max);
        }
        return max;
    }
}

Discussion:
Since we use the hash set, the time complexity is O(n) + O(n) = O(n). The space complexity is O(n) since we need n additional space to store the hash set. Please note that we must remove the found elements from the set otherwise the time complexity becomes O(mn), where m is the length of the longest consecutive sequence. 

Summary:
The problem is very tricky because it requires the upper bound of the time complexity. What we can learn from the problem is if  the problem asks for linear time solution, you should be able to think about the hash table solution. It is quite widely used in searching/matching problems.