[LeetCode] Longest Consecutive Sequence

Problem Statement (link):

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:
Apparently we are not allowed to sort the array as the fastest sorting algorithm gives us O(n lg n) complexity yet the problem requires a O(n) time complexity.

Hashing technique should come to our mind as it gives us a constant access to every entry. Suppose we build a hash map with same entries as the given array, start from one value, we could easily probe to see if the next larger value exist, if so, we continue probing the next larger value. If we traverse all entries in this manner, we will finally find the expected smallest value that starts the longest sequence.

However, the above algorithm is not ideal. Why? Imagine the following case: 4 3 5 9 1. Starting from 4, we checked 5; starting from 3, we checked 4 and 5; then we check 5 again. As you can see, there are absolutely lots of redundant probings.

One way to remove the redundancy is to remove the visited value. However, we couldn't just simply erase a value just because we visited. The reason is that we can't guarantee to find the longest sequence that has the current value. But what if we could? For each entry, suppose we not only find its larger values, but also we find its smaller values, now we are safe to remove the visited values as the longest sequence that has the current values is considered.

For instance, in the above example, if we are at entry 4, we find a larger value 5, and erase 5, and there's no 6; now we start to find the smaller value 3, and erase 3. Since there are no value 2, we are safe to say the longest sequence that contains value 3, 4 and 5 is with length 3.

The above algorithm gives us O(n) time complexity.

Code:

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()==0) return 0;

        unordered_map<int, int> hash;
        for (int i=0; i<num.size(); i++) {
            hash.emplace(num[i], 0);
        }
       
        int maxlen=1;
        for (int i=0; i<num.size(); i++) {
            int maxlen_tmp=1;
           
            // Search for the larger value
            int value = num[i]+1;
            while(hash.find(value)!=hash.end()) { // found
                hash.erase(value);
                maxlen_tmp++;
                value++;
            }
            // Search for the smaller value
            value = num[i]-1;
            while(hash.find(value)!=hash.end()) {
                hash.erase(value);
                maxlen_tmp++;
                value--;
            }

            maxlen=max(maxlen, maxlen_tmp);
        }
        return maxlen;
    }
};