Solutions

# Identify sequence starters by checking if the previous number is not in the set
# arrays
# Hash set, O(n) time, O(n) space
def longest_consecutive_sequence(nums: list[int]) -> int:
    num_set = set(nums)
    longest_streak = 0
    for num in num_set:
        if (num - 1) not in num_set:  # Only check for sequence starters
            current_num = num
            current_streak = 1
            while (current_num + 1) in num_set:
                current_num += 1
                current_streak += 1
            longest_streak = max(longest_streak, current_streak)
    return longest_streak

# Sorting, O(nlogn) time, O(1) space
def longest_consecutive_sequence(nums: list[int]) -> int:
    if not nums:
        return 0
    nums.sort()
    longest_streak = 1
    current_streak = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            current_streak += 1
        elif nums[i] != nums[i - 1]:
            longest_streak = max(longest_streak, current_streak)
            current_streak = 1
    longest_streak = max(longest_streak, current_streak)
    return longest_streak

# Brute force, O(n^2)
def longest_consecutive_sequence(nums: list[int]) -> int:
    if not nums:
        return 0
    longest_streak = 1
    for i in range(len(nums)):
        current_streak = 1
        for j in range(i + 1, len(nums)):
            if nums[j] == nums[j - 1] + 1:
                current_streak += 1
            else:
                break
        longest_streak = max(longest_streak, current_streak)
    return longest_streak