leetcode-128 Longest Consecutive Sequence

# Given an unsorted array of integers nums, return the length of the longest
# consecutive elements sequence. You must write an algorithm that runs in O(n) time.
#
# Example 1:
# Input: nums = [100,4,200,1,3,2]
# Output: 4
# Explanation: The longest consecutive sequence is [1, 2, 3, 4].
#
# Example 2:
# Input: nums = [0,3,7,2,5,8,4,6,0,1]
# Output: 9
#
# Constraints:
# 0 <= nums.length <= 10^5
# -10^9 <= nums[i] <= 10^9

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set(nums)
        max_length = 0

        for num in num_set:
            # Only start counting if this is the beginning of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_length = 1

                # Count consecutive numbers
                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1

                max_length = max(max_length, current_length)

        return max_length

    # Approach 2: Union-Find
    def longestConsecutive2(self, nums: List[int]) -> int:
        if not nums:
            return 0

        parent = {}
        size = {}

        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            root_x, root_y = find(x), find(y)
            if root_x != root_y:
                parent[root_y] = root_x
                size[root_x] += size[root_y]

        # Initialize
        for num in nums:
            if num not in parent:
                parent[num] = num
                size[num] = 1

        # Union consecutive numbers
        for num in nums:
            if num + 1 in parent:
                union(num, num + 1)

        return max(size.values())

# HashSet: Time O(n), Space O(n)
# Union-Find: Time O(n * α(n)), Space O(n)
#
# Key Insight: Only start counting from sequence start
# - For [100, 4, 200, 1, 3, 2]:
# - When we see 1: 1-1=0 not in set, so start counting: 1,2,3,4
# - When we see 2: 2-1=1 in set, skip (already counted as part of 1's sequence)
# - When we see 3: 3-1=2 in set, skip
# - When we see 4: 4-1=3 in set, skip
#
# Why O(n)?
# - Each number visited at most twice:
#   1. Once when iterating through all numbers
#   2. Once when counted as part of a sequence
# - Total: O(n) + O(n) = O(n)
#
# Alternative view: Union-Find
# - Treat as graph problem
# - Numbers are nodes
# - Edge between consecutive numbers
# - Find largest connected component
#
# AirBnB: Tests optimization thinking and O(n) solution