Longest Consecutive Sequence - Python Solution

1. Introduction

The "Longest Consecutive Sequence" problem is an intriguing challenge that involves finding the longest sequence of consecutive numbers in an unsorted array. It is a great problem for understanding the efficiency of hash tables and for practicing algorithm optimization, as the solution requires linear time complexity.

Problem

Given an unsorted array of integers nums, the task is to return the length of the longest consecutive elements sequence. The solution must run in O(n) time, which requires an approach beyond simple sorting.

2. Solution Steps

1. Create a set from the nums array for O(1) lookups.

2. Initialize a variable to keep track of the maximum length of consecutive sequences.

3. Iterate through each number in the array.

4. For each number, check if it is the start of a sequence (i.e., the number just before it is not in the array).

5. If it is the start, count the length of the consecutive sequence following it.

6. Update the maximum length if the current sequence is longer.

7. Continue this process for all numbers in the array.

8. Return the maximum length found.

3. Code Program

def longestConsecutive(nums):
    num_set = set(nums)
    max_length = 0

    for num in nums:
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            max_length = max(max_length, length)

    return max_length

# Example Usage
print(longestConsecutive([100, 4, 200, 1, 3, 2]))
print(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))

Output:

4
9

Explanation:

1. Set Conversion: Converting nums to a set enables constant-time lookups.

2. Sequence Start Check: Each number is checked to see if it's the start of a new sequence.

3. Sequence Length Calculation: For each starting number, the length of the consecutive sequence is counted.

4. Maximum Length Update: The maximum length is updated when a longer sequence is found.

5. Efficient Approach: This approach avoids sorting and directly jumps to consecutive numbers, achieving O(n) complexity.

6. Result: The function returns the length of the longest consecutive sequence in the array.