LeetCode #128 Longest Consecutiv

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Follow up: Could you implement the O(n) solution? 

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
 

Constraints:

0 <= nums.length <= 104
-109 <= nums[i] <= 109

/**
* Abstract: A close observation into the problem reveals the fact that every 
* element belongs to one and only one sequence, which means we can somehow 
* "invalidate the element after taking it into the longest consecutive 
* sequence where it belongs" (by setting it to an impossible 
* value, for example); this invalidation gives us a shorter array to traverse, 
* whose elements are collected after every call to expand.
* 
*/
void collect(int a[], int low, int n, int cn) { for (int i = low, j = 0; i < n; i++) { if (a[i] != INT_MIN) { a[j++] = a[i]; } } }

int expand(int a[], int n) {
    int len = 0, tlen = 0, left = a[0] - 1, right = left + 2;
    do {
        tlen = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == left) {
                a[i] = INT_MIN;
                tlen += 1;
                left -= 1;
            } else if (a[i] == right) {
                a[i] = INT_MIN;
                tlen += 1;
                right += 1;
            }
        }
        len += tlen;
    } while (tlen > 0);
    
    return len;
}


int longestConsecutive(int* nums, int numsSize){
    if (numsSize == 0) return 0;
    int *a = nums, n = numsSize, len = 0, cn = n;
    while (cn > 0) {
        int tlen = expand(a, cn);
        if (tlen > len) { len = tlen; }
        int ncn = cn - tlen - 1;
        collect(a, 1, cn, ncn);
        cn = ncn;
    }
    return len + 1;
}