Longest Consecutive Sequence - C Solution

1. Introduction

In this post, we explore a challenging array problem in C programming - finding the length of the longest consecutive elements sequence in an unsorted array. This problem tests the ability to implement efficient algorithms that run in linear time (O(n)) and involve advanced data structures.

Problem

Given an unsorted array of integers nums, the task is to return the length of the longest consecutive elements sequence. The challenge is to write an algorithm that runs in O(n) time complexity.

2. Solution Steps

1. Use a hash table to store each element of the array for quick lookup.

2. Iterate through each element of the array.

3. For each element, check if it's the start of a sequence (i.e., the element just before it is not in the hash table).

4. If it is the start, count the length of the consecutive sequence forward from that element.

5. Keep track of the maximum length of all such consecutive sequences.

6. Return the maximum length found.

3. Code Program

Note: Implementing an efficient solution in C for this problem requires a good hash table implementation, which is non-trivial. Below is a high-level approach:

#include <stdio.h>
#include <stdlib.h>

// Assume a hash table implementation is available
// Hash table methods: insert, exists, and createHashTable

int longestConsecutive(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    HashTable* ht = createHashTable(numsSize);
    for (int i = 0; i < numsSize; i++) {
        insert(ht, nums[i]);
    }

    int longestStreak = 0;
    for (int i = 0; i < numsSize; i++) {
        if (!exists(ht, nums[i] - 1)) {
            int currentNum = nums[i];
            int currentStreak = 1;

            while (exists(ht, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = longestStreak > currentStreak ? longestStreak : currentStreak;
        }
    }

    freeHashTable(ht);
    return longestStreak;
}

int main() {
    int nums[] = {100, 4, 200, 1, 3, 2};
    int length = sizeof(nums) / sizeof(nums[0]);
    printf("Longest Consecutive Sequence: %d\n", longestConsecutive(nums, length));
    return 0;
}

Output:

Longest Consecutive Sequence: 4

Explanation:

1. Create a hash table and insert all elements of the array.

2. Iterate through the array, checking for the start of a new sequence.

3. If a number is the start, count the length of the consecutive sequence.

4. Update the maximum length if a longer sequence is found.

5. Return the maximum length after checking all elements.

6. The main function demonstrates the algorithm with an example.