Problem Statement

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.

Additional information

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Example 1:

Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4

Example 2:

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

Output: 9

Brute Force

Intuition
The simplest approach is to consider every number in the array as the potential start of a sequence. For each number x, we check if x + 1 exists in the array, then x + 2, and so on, counting the length of the sequence until we can't find the next number. We do this for every single number and keep track of the longest sequence found.

Algorithm

1. Initialize longest_streak to 0.
2. Iterate through each number num in the array nums.
3. For each num, set current_num to num and current_streak to 1.
4. While current_num + 1 exists in the array:

• Increment current_num and current_streak.

5. Update longest_streak with the maximum of longest_streak and current_streak.
6. Return longest_streak.

def longest_consecutive(nums: list[int]) -> int:
    longest_streak = 0

    for num in nums:
        current_num = num
        current_streak = 1

        while current_num + 1 in nums:
            current_num += 1
            current_streak += 1

        longest_streak = max(longest_streak, current_streak)

    return longest_streak

Time & Space Complexity

• Time complexity: O(n^3)

• Reason: The outer loop runs n times. The while loop can run up to n times in the worst case (e.g., if the sequence is 1, 2, 3... n). The in operator in Python lists takes O(n) time. Total: O(n * n * n).

• Space complexity: O(1)

• Reason: We only use a few variables for tracking streaks.

Sorting

Intuition
If the array were sorted, consecutive elements would be adjacent to each other. We could simply iterate through the sorted array and count the length of the current consecutive sequence, resetting the count whenever the sequence breaks. While this is intuitive and faster than brute force, sorting takes O(n log n), which does not meet the O(n) requirement.

Algorithm

1. If the array is empty, return 0.
2. Sort the array.
3. Initialize longest to 1 and current_streak to 1.
4. Iterate through the sorted array from index 1.
5. If the current number is the same as the previous one, skip it (duplicates don't break or extend a sequence).
6. If the current number is exactly 1 greater than the previous one, increment current_streak.
7. Otherwise, update longest with the max of longest and current_streak, and reset current_streak to 1.
8. Return the maximum of longest and current_streak.

def longest_consecutive(nums: list[int]) -> int:
    if not nums:
        return 0
    
    nums.sort()
    longest = 1
    current_streak = 1
    
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue
            
        if nums[i] == nums[i - 1] + 1:
            current_streak += 1
        else:
            longest = max(longest, current_streak)
            current_streak = 1
            
    return max(longest, current_streak)

Time & Space Complexity

• Time complexity: O(n log n)

• Reason: The sorting operation dominates the complexity.

• Space complexity: O(1) or O(n)

• Reason: Depends on the sorting implementation (e.g., Python's Timsort uses O(n)).

Hash Set (Optimal)

Intuition
To achieve O(n) time, we can use a Hash Set to allow O(1) lookups. The key insight is to identify the start of a sequence. A number x is the start of a sequence if x - 1 does not exist in the set. Once we find a start, we can simply count upwards (x + 1, x + 2, ...) to find the length of that specific sequence. This ensures we only visit each sequence once.

Algorithm

1. Create a set num_set from nums to remove duplicates and allow O(1) lookups.
2. Initialize longest to 0.
3. Iterate through each number n in the set.
4. Check if n - 1 exists in the set.

• If it does, then n is not the start of a sequence, so we skip it.
• If it does not, then n is the start of a sequence.

5. If n is a start, check for n + 1, n + 2, etc., increasing the length count until the sequence breaks.
6. Update longest with the maximum length found.
7. Return longest.

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    
    for n in num_set:
        # Check if 'n' is the start of a sequence
        if (n - 1) not in num_set:
            length = 0
            while (n + length) in num_set:
                length += 1
            longest = max(length, longest)
            
    return longest

Time & Space Complexity

• Time complexity: O(n)

• Reason: Although there is a while loop inside the for loop, each number is visited at most twice: once by the for loop and once by the while loop (only if it's part of a valid sequence lookup).

• Space complexity: O(n)

• Reason: We use a set to store all unique elements of the array.