5 Best Ways to Find Length of Longest Consecutive Sequence in Python

Rate this post

πŸ’‘ Problem Formulation: Given an unsorted array of integers, the goal is to find the length of the longest consecutive elements sequence. For example, if the input array is [100, 4, 200, 1, 3, 2], the longest consecutive elements sequence is [1, 2, 3, 4], and the desired output is 4.

Method 1: Using Sorting

This method involves sorting the array which allows consecutive elements to be positioned adjacent to each other. Once sorted, we iterate over the array to find the longest consecutive sequence. This approach is simple and works well but is not the most efficient due to the sorting step.

Here’s an example:

def longest_consecutive(nums):
    if not nums:
        return 0
    
    nums.sort()
    longest = 1
    current = 1
    
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            if nums[i] == nums[i - 1] + 1:
                current += 1
            else:
                longest = max(longest, current)
                current = 1
                
    return max(longest, current)

# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output: 4

This code snippet starts by handling the edge case where the input list is empty. After sorting the array, we iterate over it, tracking the length of the current consecutive sequence and updating the longest as needed. The final result is obtained by comparing the length of the last sequence with the previously stored longest length.

Method 2: Using HashSet

HashSet-based method exploits the constant time complexity of lookup operations. By storing the elements in a set, we can check for consecutive sequences without sorting. This is more efficient than Method 1, especially for large datasets, since it operates in linear time complexity.

Here’s an example:

def longest_consecutive(nums):
    nums_set = set(nums)
    longest = 0
    
    for n in nums:
        if n - 1 not in nums_set:
            length = 0
            while (n + length) in nums_set:
                length += 1
            longest = max(longest, length)
    
    return longest

# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output: 4

The code creates a set from the input list and then iterates through the list. For each element, it checks if it’s the start of a sequence (previous number not in set). Then it counts the consecutive numbers using a while loop and updates the longest sequence length accordingly.

Method 3: Using Dictionary

This method utilizes a dictionary to keep track of sequence boundaries. For each number, it updates the sequence length stored at the sequence start and end in the dictionary. This allows finding the longest consecutive sequence efficiently in linear time without the need for sorting.

Here’s an example:

def longest_consecutive(nums):
    seq_dict = {}
    max_length = 0
    for num in nums:
        if num not in seq_dict:
            left = seq_dict.get(num - 1, 0)
            right = seq_dict.get(num + 1, 0)
            length = 1 + left + right
            seq_dict[num] = length
            seq_dict[num - left] = length
            seq_dict[num + right] = length
            max_length = max(max_length, length)
    return max_length

# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output: 4

The code initializes a dictionary that will store the lengths of sequences. As we iterate through each number, we update the dictionary entries for the start and end of the sequence. The maximum length found during this process is the length of the longest consecutive sequence.

Method 4: Dynamic Programming

Dynamic Programming can be applied to this problem by memorizing the length of the consecutive sequence for each number in a way that updates the sequence lengths efficiently by considering only those elements which start a new sequence. It’s similar to the dictionary method but focuses on a more algorithmic approach to managing state.

Here’s an example:

# This method is conceptual and might not be the most effective to use directly.
# See Method 3 for a practical application of this concept using a dictionary.

# Other methods would involve actual code.

No output provided as this method is conceptual.

This section introduces the concept of using Dynamic Programming to solve the problem. However, in practice, the techniques provided in Method 3 with dictionaries can be considered a form of dynamic programming, as it effectively breaks down the problem into state-based subproblems.

Bonus One-Liner Method 5: Using Comprehensions and Sets

This one-liner method combines list comprehensions and set operations to find the longest consecutive sequence. It’s a condensed version of Method 2, achieving the same result with fewer lines of code, but might compromise readability.

Here’s an example:

longest_consecutive = lambda nums: max((len(list(iter(lambda x=n: x not in s or s.remove(x) or x, range(1, len(s)))))) for n in set(nums)) if nums else 0

# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output: 4

This one-liner uses a set for its input and a generator expression with an embedded lambda function and iter() to find the length of the longest consecutive sequence. While it may be clever, such compressed code could hinder the understanding and maintainability of the code, especially for those not familiar with Python’s more advanced constructs.

Summary/Discussion

  • Method 1: Sorting. Simple and intuitive. However, it requires O(n log n) time due to sorting, which is suboptimal for large arrays.
  • Method 2: HashSet. More efficient with a linear O(n) time complexity. However, additional space complexity is involved due to using a set.
  • Method 3: Dictionary. Similar advantages to the HashSet method with an O(n) time complexity but uses a dictionary for more explicit sequence tracking.
  • Method 4: Dynamic Programming. Conceptually strong and algorithmically robust. Practical implementation overlaps with the dictionary method’s logic.
  • Bonus Method 5: One-Liner. Concise and elegant but potentially confusing for less experienced programmers.