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: This solution's based on the idea of hashing:
* for every element a[i], we bidirectionally construct the consecutive
* sequence by:
* 1) checking the presences of a[i] + 1, a[i] + 2..., and then
* 2) checking the presences of a[i] - 1, a[i] - 2...
* during which, we zero out the flags for every element checked thus
* sparing us the duplicate checking for the elements in the same 
* sequence.
* NOTE: The hash map SeparateChainingHashST type is given at the end of this article,
* which is implemented, as implied by its name, as a symbol table with hash using 
* separate chaining collision resolution.
* 
*/
#define PRIME 21089
int longestConsecutive(int* nums, int numsSize){
    if (numsSize == 0) return 0;
    int *a = nums, n = numsSize;
    SeparateChainingHashST flags = CreateSeparateChainingHashST(PRIME);
    int max = INT_MAX, min = INT_MIN;
    for (int i = 0; i < n; i++) { SetSCHST(flags, *(a + i), true); }
    int len = 1, tlen = 0, ai, t;
    for (int i = 0; i < n; i++) {
        ai = *(a + i);
        if (GetSCHST(flags, ai)) {
            SetSCHST(flags, ai, false);
            tlen = 1;
            t = ai + 1;
            while (GetSCHST(flags, t)) {
                SetSCHST(flags, t, false);
                tlen++;
                t++;
            } 
            t = ai - 1;
            while (GetSCHST(flags, t)) {
                SetSCHST(flags, t, false);
                tlen++;
                t--;
            } 
            if (len < tlen) { len = tlen; }
        }
    }
    return len;
}

/**
* Abstract: A hash map, use separate chaining to resolve hash collisions.
* Reference: Algorithms, 4ed, by R. Sedgewick & Kevin Wayne
*/
typedef int Key;
typedef bool Value;
typedef struct Node {
    Value val;
    Key key;
    struct Node *next;
}*NodePtr;
typedef NodePtr SequentialSearchST;

/**
* Support set key/value to a empty list(NULL), under which circumstance a new 
* list's returned.
*/
SequentialSearchST SetSSST(SequentialSearchST st, Key key, Value val) {
    struct Node *node = st;
    while (node != NULL) {
        if (node->key == key) {
            node->val = val;
            return st;
        }
        node = node->next;
    }
    node = (struct Node*)malloc(sizeof*node);
    node->key = key;
    node->val = val;
    node->next = st;
    return node;
}

/**
 * Return 0 for empty list(NULL) and absent keys.
*/
int GetSSST(SequentialSearchST st, Key key) {
    struct Node *node = st;
    while (node != NULL) {
        if (node->key == key) { return node->val; }
        node = node->next;
    }
    return 0;
}

SequentialSearchST RemoveSSST(SequentialSearchST st, Key key) {
    if (st == NULL) return NULL;
    struct Node *node = st;
    if (node->key == key) {
        st = node->next;
        free(node);
        return st;
    }
    struct Node *next = st->next;
    while (next != NULL) {
        if (next->key == key) {
            node->next = next->next;
            free(next);
            return st;
        }
        node = next;
        next = node->next;
    }
    return st;
}

typedef struct SeparateChainingHashSTStruct {
    int M;
    SequentialSearchST *st;
}* SeparateChainingHashST;

int Hash(Key key, int M) { return key < 0 ? -key % M : key % M; }

SeparateChainingHashST CreateSeparateChainingHashST(int M) {
    SeparateChainingHashST hst = (SeparateChainingHashST)malloc(sizeof(*hst));
    hst->M = M;
    hst->st = (SequentialSearchST*)malloc(M * sizeof(*(hst->st)));
    for (int i = 0; i < M; i++) { hst->st[i] = NULL; }
    return hst;
}

void SetSCHST(SeparateChainingHashST hst, Key key, Value val) { 
    int hash = Hash(key, hst->M);
    hst->st[hash] = SetSSST(hst->st[hash], key, val); 
}

int GetSCHST(SeparateChainingHashST hst, Key key) { return GetSSST(hst->st[Hash(key, hst->M)], key); }

void RemoveSCHST(SeparateChainingHashST hst, Key key) {
    int hash = Hash(key, hst->M);
    hst->st[hash] = RemoveSSST(hst->st[hash], key);
}