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.

---

Since the problem asked us to solve it in O(n), we cannot use any sort-based approach. Hence, we need to find a way to record the current longest sequence. A hashmap can be used here. Each time a element is inserted to the map, we check to see if element-1 is in the map. If it exists, we set the value of element to map[element-1]+1. Then we check to see if element+1 is in the map. It it exists, we update the value of element and the end of sequence starting from element+1. At the end, we can reset the value of the starting element in the sequence. Until now, the starting element and ending element of the sequence have the latest length info.

C++ Code:

/*
 * func: longest_consecutive
 * goal: find the longest consecutive sequence
 * @param num: input number array
 * return: the length of longest consecutive sequence
 */
int longest_consecutive(vector<int> &num){
    int max_length = 0;
    unordered_map<int, int> count_helper;
    for(const int &number : num){
        if(count_helper.find(number) != count_helper.end()){
            continue;
        }
        count_helper[number] = 1;
        
        //If the previous value is in the map, connection them together
        if(count_helper.find(number-1) != count_helper.end()){
            count_helper[number] = count_helper[number-1] + 1;
        }
        //If the next value is in the map, update the biggest number's value
        if(count_helper.find(number+1) != count_helper.end()){
            int last = number+1+count_helper[number+1]-1;
            count_helper[number] = count_helper[last] = count_helper[number] + count_helper[last];
        }
        //Update the count of the smallest value in the chain
        if(count_helper.find(number-1) != count_helper.end()){
            int first = number-1-count_helper[number-1]+1;
            count_helper[first] = count_helper[number];
        }
        
        max_length = max(max_length, count_helper[number]);
    }
    return max_length;
}

Python Code:

# func: find the longest consecutive sequence
# @param num: input number list
# @return: the length of the sequence
def longest_consecutive(num):
    count_helper = {}
    max_length = 0
    for number in num:
        if number not in count_helper:
            count_helper[number] = 1

            #Find if number-1 is in the map
            if number-1 in count_helper:
                count_helper[number] = count_helper[number-1] + 1

            #Find if number+1 in the map
            if number+1 in count_helper:
                #Find the last element starting from number+1
                last = count_helper[number+1] + number
                #Update the value in last and number
                count_helper[last] = count_helper[number] = count_helper[number] + count_helper[last]
            #Find the start position of the sequence
            if number-1 in count_helper:
                first = number - count_helper[number-1]
                count_helper[first] = count_helper[number]

            max_length = max(max_length, count_helper[number])

    return max_length