LeetCode Solutions Blog

Longest Consecutive Sequence

Number: 128

Difficulty: Medium

Paid? No

Problem Description

Given an unsorted array of integers, return the length of the longest consecutive elements sequence. The algorithm must run in O(n) time.

Key Insights

Utilize a set (or hash table) for constant time look-ups.
Only start counting a sequence from a number that is the beginning (its previous number is not in the set).
Each number is visited only once, ensuring an O(n) time complexity.
Update the maximum sequence length as you discover longer consecutive sequences.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We first insert all the numbers into a hash set to enable O(1) membership checks. For each number in the set, we check if it is the start of a sequence by ensuring that the number minus one is not in the set. If it is the beginning, we then count all consecutive numbers following it, updating the maximum sequence length when necessary. This method guarantees that we only count each number once, satisfying the O(n) time requirement.

Code Solutions

# Python solution for Longest Consecutive Sequence

def longestConsecutive(nums):
    # Create a set from the list for O(1) look-up times
    num_set = set(nums)
    longest_streak = 0
    
    # Iterate through each number in the set
    for num in num_set:
        # Only start counting if 'num-1' is not present in the set
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1
            
            # Count consecutive numbers starting from current_num
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1
                
            # Update the longest streak if current one is longer
            longest_streak = max(longest_streak, current_streak)
    
    return longest_streak

# Example usage:
print(longestConsecutive([100, 4, 200, 1, 3, 2]))  # Output: 4