[Leetcode] 128. Longest Consecutive Sequence

문제

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

You must write an algorithm that runs in O(n) time.

 

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

 

풀이

 

qsort를 사용하면 time complexity가 nlog(n)이 되므로 사용할 수 없다.

핵심은 hash table을 사용해 빠르게 필요한 숫자(num+1 || num-1)를 찾고, 찾았다면 없애는 것이다. 

 

두개의 while loop을 사용한 이유는 보통 아래의 코드를 사용할 텐데: 

// Find longest consecutive sequence
    for (int i = 0; i < numsSize; i++) {
        if (!searchHash(table, nums[i] - 1)) { // (*****Start of a sequence *****) - avoid repeating
            int currentNum = nums[i];
            int currentLen = 1;

            while (searchHash(table, currentNum + 1)) { // Check next numbers - assuming currentNum is the smallest num of consecutive nums
                currentNum++;
                currentLen++;
            }

            maxLen = (currentLen > maxLen) ? currentLen : maxLen;
        }
    }

 

이 코드는 repeated number가 많을 때 에러가 난다.

예를 들어, this passes if the input is an array of [1,2,3,4,...,49999, 50000]. 

However, this does not pass if the input is an array of [1,2,3,4,...,49999, 50000, 0,0,0,0,0,0,0,0,0,...,0]. (0의 갯수가 클 때)

 

We know the number should be removed if it was searched. 

하지만 첫 번째로 찾은 숫자가 consecutive numbers 상의 가장 작은 숫자가 아닐때 없애버리면 max consecutive number를 찾지 못하므로, 한번에 모든 consecutive numbers를 찾기위해 2개의 while loop이 필요하다.

 

코드

 

Simpler code: 

typedef struct HashNode{ 
    int key;
    struct HashNode * next;
} HashNode;

typedef struct HashTable{ 
    HashNode** buckets;
    int size;
} HashTable;

int hashfunction(int key, int size) {
    return abs(key)%size;
}

HashTable* createTable(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = (HashNode**)calloc(size, sizeof(HashNode*));
    return table;
}

void insertTable(HashTable* table, int key) {
    int index = hashfunction(key, table->size);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->next = table->buckets[index];
    table->buckets[index] = node;
}
bool searchNode(HashTable* table, int key) {
    int index = hashfunction(key, table->size);
    HashNode* curr = table->buckets[index];
    while(curr) {
        if(curr->key == key) {
            curr->key = INT_MIN; // remove the number
            return true;
        }
        curr = curr->next;
    }
    return false;
}

void freeTable(HashTable * table) {
    for(int i=0; i<table->size; i++){
        HashNode* curr = table->buckets[i];
        while(curr) {
            HashNode* temp = curr->next;
            free(curr);
            curr = temp;
        }
    }
    free(table->buckets);
    free(table);
}
int longestConsecutive(int* nums, int numsSize) {
    // int tableSize = (numsSize > 30000)? 30000 : numsSize;
    int tableSize = numsSize;
    HashTable* table = createTable(tableSize);

    // create table
    for(int i=0; i<tableSize; i++) {
        insertTable(table, nums[i]);
    }

    int longest = 0;
    // search longest consec
    for(int i=0; i<tableSize; i++) {
        int num = nums[i];
        int j = 1;
        int consec = 1;

        while(searchNode(table, num-j)) {
            consec++;
            j++;
        }
        j=1;
        while(searchNode(table, num+j)) {
            consec++;
            j++;
        }
        longest = (longest < consec)? consec : longest;
    }
    freeTable(table);
    return longest;
}

 

* 여기서 숫자를 제거하는 코드는 간단히 가장 작은 숫자(INT_MIN)로 대체되었지만, linked list에서 제거하는 것이 logic이 맞다.

 

 

Correct code: (less runtime!)

typedef struct HashNode{ 
    int key;
    struct HashNode * next;
} HashNode;

typedef struct HashTable{ 
    HashNode** buckets;
    int size;
} HashTable;

int hashfunction(int key, int size) {
    return abs(key)%size;
}

HashTable* createTable(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->size = size;
    table->buckets = (HashNode**)calloc(size, sizeof(HashNode*));
    return table;
}

void insertTable(HashTable* table, int key) {
    int index = hashfunction(key, table->size);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->next = table->buckets[index];
    table->buckets[index] = node;
}
bool searchNode(HashTable* table, int key) {
    int index = hashfunction(key, table->size);
    HashNode* curr = table->buckets[index];
    while(curr) {
        if(curr->key == key) {
            curr->key = INT_MIN; // remove the number
            return true;
        }
        curr = curr->next;
    }
    return false;
}

// Search and remove from hash table
bool searchAndRemove(HashTable* table, int key) {
    int index = hashfunction(key, table->size);
    HashNode* curr = table->buckets[index];
    HashNode* prev = NULL;

    while (curr) {
        if (curr->key == key) {
            // Remove node from linked list
            if (prev) {
                prev->next = curr->next;
            } else {
                table->buckets[index] = curr->next;
            }
            free(curr);
            return true;
        }
        prev = curr;
        curr = curr->next;
    }
    return false;
}

void freeTable(HashTable * table) {
    for(int i=0; i<table->size; i++){
        HashNode* curr = table->buckets[i];
        while(curr) {
            HashNode* temp = curr->next;
            free(curr);
            curr = temp;
        }
    }
    free(table->buckets);
    free(table);
}

int longestConsecutive(int* nums, int numsSize) {
    // int tableSize = (numsSize > 30000)? 30000 : numsSize;
    int tableSize = numsSize;
    HashTable* table = createTable(tableSize);

    // create table
    for(int i=0; i<tableSize; i++) {
        insertTable(table, nums[i]);
    }

    int longest = 0;
    // search longest consec
    for(int i=0; i<tableSize; i++) {
        int num = nums[i];
        int j = 1;
        int consec = 1;

        while(searchAndRemove(table, num-j)) {
            consec++;
            j++;
        }
        j=1;
        while(searchAndRemove(table, num+j)) {
            consec++;
            j++;
        }
        longest = (longest < consec)? consec : longest;
    }
    freeTable(table);
    return longest;
}