Finding the Longest Consecutive Sequence in a List
In many programming scenarios, one might encounter the need to identify the longest consecutive sequence of integers within a list. This problem can be efficiently solved using a set for quick lookups, and the overall time complexity can be kept at O(n).
Below is a Python function that implements this logic:
def longest_consecutive_sequence(nums):
if not nums:
return []
# Convert the list to a set for O(1) lookups
num_set = set(nums)
longest_sequence = []
for num in num_set:
# Only check for sequences starting with the smallest number
if num - 1 not in num_set:
current_num = num
current_sequence = [current_num]
# Build the sequence from the current number
while current_num + 1 in num_set:
current_num += 1
current_sequence.append(current_num)
# Update the longest_sequence if current_sequence is longer
if len(current_sequence) > len(longest_sequence):
longest_sequence = current_sequence
return longest_sequence
# Example usage:
example_list = [100, 4, 200, 1, 3, 2]
print(longest_consecutive_sequence(example_list)) # Output: [1, 2, 3, 4]
Explanation of the Code
1. Input Check: First, the function checks if the input list is empty. If it is, an empty list is returned.
2. Convert to Set: The input list nums is converted to a set called num_set. This conversion allows for O(1) average time complexity for membership checks, which increases the efficiency of the algorithm.
3. Iterate Over Unique Numbers: The function iterates through each number in num_set. For each number, it checks whether it is the start of a sequence by verifying that num - 1 is not present in num_set.
4. Build Sequence: If the number is the starting point, the function initializes current_num and current_sequence. It then enters a loop, checking for consecutive integers (current_num + 1). Each consecutive number is added to the current_sequence.
5. Update Longest Sequence: After building a complete sequence, the function compares the length of current_sequence with longest_sequence. If the current is longer, it updates longest_sequence.
6. Return Result: Finally, the function returns the longest found sequence.
Example Usage
The provided example demonstrates how to use the function. The list [100, 4, 200, 1, 3, 2] results in the longest consecutive sequence [1, 2, 3, 4].
This function is efficient and handles sequences of varying sizes and orders, making it a useful tool for analyzing numeric datasets.