class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
"""
Determine the length of the longest consecutive sequence in an unsorted array of integers.
Parameters:
nums (List[int]): A list of integers which can include positive, negative, and zero.
Returns:
int: The length of the longest sequence of consecutive numbers found in the list.
"""
num_set = set(nums) # Convert list to a set for O(1) lookups.
longest = 0 # Initialize the variable to track the maximum consecutive sequence length.
# Iterate over each unique number in the set.
for num in num_set:
# Check if the current number is the start of a sequence.
# If num - 1 is not in the set, then num could be the beginning.
if num - 1 not in num_set:
current = num # The starting number of a potential sequence.
current_streak = 1 # The length of the current sequence, starting at 1.
# While the next consecutive number exists in the set, extend the sequence.
while current + 1 in num_set:
current += 1 # Move to the next consecutive number.
current_streak += 1 # Increment the current sequence length.
# Update the longest consecutive sequence length if the current one is larger.
longest = max(longest, current_streak)
return longest
Summary of Techniques and Approaches:
Set-Based Lookup: Utilizing a set for O(1) average time complexity when checking for existence of elements is key. This technique is widely applicable in problems requiring fast membership testing.
Sequence Start Identification: The condition if num - 1 not in num_set ensures that each sequence is only counted once from its starting point. This minimizes redundant computations and guarantees O(n) time complexity.
Single Pass Expansion: For each potential sequence start, the solution expands the consecutive sequence in a while loop until it no longer exists. This strategy of expanding from a seed element can be applied to various problems that involve contiguous or relational data spread across a collection.
General Application: Recognize scenarios where similar set-based approaches can avoid unnecessary iterations, such as finding unique elements, deduplication, or solving connected component problems. This method is particularly useful when the order of elements doesn’t matter or can be rearranged for efficiency.