Longest Consecutive Sequence

December 25, 2023

Problem #

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

Solution #

To solve the problem of finding the length of the longest consecutive elements sequence in an unsorted array of integers, we can use a hash set for efficient lookups. The algorithm involves iterating through the array and dynamically checking for consecutive sequences. Here’s how we can implement it in Python:

def longest_consecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    longest_streak = 0

    for num in num_set:
        # Check if it's the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # Increment the streak while the next consecutive number is found
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

    return longest_streak

# Example Usage
example_array = [100, 4, 200, 1, 3, 2]
print("Length of the longest consecutive elements sequence is:", longest_consecutive(example_array))

In this code:

• We first convert the array into a set for O(1) lookup times.
• We then iterate through each number in the set.
• For each number, we check if it’s the start of a new sequence (i.e., there is no preceding number in the set).
• If it is the start of a new sequence, we then count how many consecutive numbers follow it.
• We keep track of the length of the longest sequence found so far.

This approach ensures that each sequence is only counted once and does so efficiently, resulting in an overall time complexity of O(n) for the algorithm, where n is the number of elements in the array.