[LeetCode/Python] 128. Longest Consecutive Sequence

📌 Problem

[LeetCode] 128. Longest Consecutive Sequence

📌 Solution

Solution 1: Original Idea (Sort + Scan)

Idea

• Remove duplicates and sort the array.
• Traverse numbers from left to right.
• Keep a start_idx that marks the beginning of the current consecutive sequence.
• While iterating:
  • If the next number is not equal to current + 1, the sequence breaks.
  • Compute the sequence length using the distance from start_idx to the current index.
  • Update the local maximum length.
  • Reset start_idx to the next index.
• Handle the last element separately since it has no next index.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = sorted(set(nums))
        longest = 0
        length = 0
        start_idx = 0
        
        for i, curr in enumerate(num_set):
            if i >= len(num_set) - 1:
                length = i - start_idx + 1
            elif curr + 1 != num_set[i+1]:
                length = i - start_idx + 1
                start_idx = i+1
            longest = max(longest, length) 

        return longest

Complexity

• Time Complexity: $O(n \log n)$
• Space Complexity: $O(n)$

Solution 2: Upgraded Version (Still Sort + Scan)

Idea

• Keep the same sort + scan strategy.
• Instead of tracking indices (start_idx), directly track the current sequence length.
• While iterating:
  • If the current number is consecutive (prev + 1), increment length.
  • Otherwise, update longest and reset length to 1.
• This simplifies logic and avoids index-based calculations.

Code

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

        num_set = sorted(set(nums))  # unique + sort
        longest = 1
        length = 1

        for i in range(1, len(num_set)):
            if num_set[i] == num_set[i - 1] + 1:
                length += 1
            else:
                longest = max(longest, length)
                length = 1

        return max(longest, length)

Complexity

• Time Complexity: $O(n \log n)$
• Space Complexity: $O(n)$

⭐️ Solution 3: Optimal Solution (HashSet, O(n))

Idea

• Insert all numbers into a hash set for $O(1)$ lookup.
• Only start counting when the current number is the start of a sequence
  (i.e., num - 1 does not exist in the set).
• From the start, expand forward (num + 1, num + 2, ...) to count the sequence length.
• Each number is visited at most once during expansion.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for num in num_set:
            # start of sequence
            if num - 1 not in num_set:
                length = 1
                curr = num

                while curr + 1 in num_set:
                    curr += 1
                    length += 1

                longest = max(longest, length)

        return longest

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$