Longest Consecutive Sequence medium

Problem Statement

Given an unsorted array of integers nums, find 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

Steps:

1. Create a Set: Convert the input array nums into a set. Sets provide O(1) lookup time, which is crucial for achieving the O(n) time complexity.

2. Iterate and Check: Iterate through each number in the set.

3. Check for Start of Sequence: For each number, check if it's the start of a consecutive sequence (meaning the number num - 1 is not present in the set).

4. Extend Sequence: If it's the start of a sequence, start extending the sequence by checking for num + 1, num + 2, and so on, until you find a number that's not present in the set. Count the length of the sequence.

5. Update Maximum: Keep track of the maximum length encountered so far.

Explanation:

The key to achieving O(n) time complexity is using a set. A naive approach of sorting the array and then finding the longest consecutive sequence would take O(n log n) time due to the sorting step. By using a set, we can efficiently check for the presence or absence of a number in constant time. The algorithm iterates through the array only once, performing constant-time operations for each number, resulting in a linear time complexity.

Code:

def longestConsecutive(nums):
    num_set = set(nums)  # Convert to set for O(1) lookup
    max_length = 0

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

            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1

            max_length = max(max_length, current_length)

    return max_length

Complexity:

• Time Complexity: O(n) - The algorithm iterates through the set once. While the inner while loop might seem problematic, each element is only visited once in the entire process (it's only entered if it's part of a sequence and its predecessor isn't). Therefore, the nested loop doesn't increase the overall time complexity beyond linear.

• Space Complexity: O(n) - In the worst case, the set num_set will store all the numbers from the input array.