LeetCode 128: Longest Consecutive Sequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 128: Longest Consecutive Sequence?

In LeetCode 128: Longest Consecutive Sequence, you’re given an unsorted array of integers nums, and your task is to find the length of the longest consecutive sequence within it. A consecutive sequence is a run of numbers where each number increases by 1 (e.g., 1, 2, 3). The array can contain duplicates, and you need to return the length, not the sequence itself. For example, with nums = [100, 4, 200, 1, 3, 2], the longest sequence is 1, 2, 3, 4, so the output is 4.

Problem Statement

• Input: An integer array nums.
• Output: An integer—the length of the longest consecutive sequence.
• Rules:
• Numbers must differ by 1 (e.g., n, n+1, n+2).
• Sequence can appear in any order in the array.
• Handle duplicates efficiently.

Constraints

• 0 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹

Examples

• Input: nums = [100, 4, 200, 1, 3, 2]
• Output: 4
• Why: Sequence 1, 2, 3, 4 has length 4.
• Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
• Output: 9
• Why: Sequence 0, 1, 2, 3, 4, 5, 6, 7, 8 has length 9.
• Input: nums = []
• Output: 0
• Why: Empty array has no sequence.

Understanding the Problem: Finding the Longest Streak

To solve LeetCode 128: Longest Consecutive Sequence in Python, we need to identify the longest run of consecutive numbers in an unsorted array, accounting for duplicates and large ranges. A naive approach—checking every possible starting number—would take O(n²) time, which is too slow for 10⁵ elements. Instead, we’ll use optimized techniques:

• Best Solution (Hash Set): O(n) time, O(n) space—checks sequences smartly.
• Alternative Solution (Sorting): O(n log n) time, O(1) space—sorts first.

Let’s dive into the Best Solution—the hash set approach—and break it down step-by-step.

Best Solution: Hash Set with Sequence Tracking

Why This Is the Best Solution

The hash set approach is the champion because it achieves O(n) time complexity with O(n) space, making it incredibly efficient. It uses a set to store all numbers, then only checks potential sequence starts, avoiding redundant work. It’s like scanning a crowd for the leader of each group, then counting their followers—fast, smart, and elegant!

How It Works

Here’s the strategy:

• Step 1: Build a Set:
• Convert nums to a set to remove duplicates and enable O(1) lookups.
• Step 2: Find Sequence Starts:
• For each number, check if it’s the start of a sequence (no num-1 in set).
• Step 3: Count Sequences:
• From each start, count consecutive numbers (num+1, num+2, etc.) in set.
• Track the longest count.
• Step 4: Return:
• Return the maximum length found.

Why O(n)? Each number is checked once as a potential start, and each is part of at most one full sequence count, amortizing to linear time.

Step-by-Step Example

Example: nums = [100, 4, 200, 1, 3, 2]

• Step 1: Build Set:
• num_set = {1, 2, 3, 4, 100, 200}.
• Step 2: Check Each Number:
• 100: 99 not in set, start sequence.
• 101 not in set, length = 1.
• 4: 3 in set, not a start, skip.
• 200: 199 not in set, start sequence.
• 201 not in set, length = 1.
• 1: 0 not in set, start sequence.
• 2, 3, 4 in set, 5 not in set, length = 4.
• 3: 2 in set, skip.
• 2: 1 in set, skip.
• Step 3: Track Max:
• Lengths: 1 (100), 1 (200), 4 (1).
• max_length = 4.
• Result: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # Step 1: Build set
        num_set = set(nums)

        # Step 2: Initialize max length
        max_length = 0

        # Step 3: Check each potential sequence start
        for num in num_set:
            # Only start if num-1 not in set
            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

                # Update max length
                max_length = max(max_length, current_length)

        return max_length

• Line 4: Convert nums to set for O(1) lookups.
• Line 7: Initialize max_length.
• Line 10-18: Loop through numbers:
• Line 11: Check if start of sequence.
• Line 12-15: Count sequence length.
• Line 18: Update max.
• Line 20: Return result.
• Time Complexity: O(n)—each number checked once, sequence counts amortized.
• Space Complexity: O(n)—size of set.

This is a sequence-spotting wizard!

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach is a simpler fallback—O(n log n) time, O(1) space (excluding sort space)—sorting the array first, then scanning for consecutive runs. It’s like lining up the numbers in order and counting how long each streak lasts—intuitive but slower due to sorting.

How It Works

• Step 1: Sort the array, handle empty case.
• Step 2: Scan sorted array, track consecutive runs.
• Step 3: Return longest run length.

Step-by-Step Example

Example: nums = [100, 4, 200, 1, 3, 2]

• Step 1: Sort:
• nums = [1, 2, 3, 4, 100, 200].
• Step 2: Scan:
• 1 → 2: length = 2.
• 2 → 3: length = 3.
• 3 → 4: length = 4.
• 4 → 100: gap, reset length = 1.
• 100 → 200: length = 2.
• Step 3: Max:
• Lengths: 4, 2.
• max_length = 4.
• Result: 4.

Code for Sorting Approach

Copy codeclass Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # Handle empty case
        if not nums:
            return 0

        # Step 1: Sort array
        nums.sort()

        # Step 2: Track consecutive runs
        max_length = 1
        current_length = 1

        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:  # Skip duplicates
                continue
            elif nums[i] == nums[i-1] + 1:  # Consecutive
                current_length += 1
                max_length = max(max_length, current_length)
            else:  # Gap
                current_length = 1

        return max_length if len(nums) > 0 else 0

• Line 4-5: Return 0 for empty array.
• Line 8: Sort array.
• Line 11-19: Scan for runs:
• Line 14: Skip duplicates.
• Line 16-17: Increment for consecutive.
• Line 19: Reset on gap.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—no extra space (sort in-place).

It’s a sorted streak counter!

Comparing the Two Solutions

• Hash Set (Best):
• Pros: O(n) time, O(n) space, fast and elegant.
• Cons: Uses extra space.
• Sorting (Alternative):
• Pros: O(n log n) time, O(1) space, simple logic.
• Cons: Slower due to sorting.

Hash set wins for speed.

Additional Examples and Edge Cases

• [1, 2, 2, 3]: 3 (1, 2, 3).
• [1]: 1.
• [4, 3, 2]: 3.

Both handle these perfectly.

Complexity Breakdown

• Hash Set: Time O(n), Space O(n).
• Sorting: Time O(n log n), Space O(1).

Hash set’s linear time shines.

Key Takeaways

• Hash Set: Spot starts, count fast!
• Sorting: Line up and scan!
• Sequences: Consecutive is key.
• Python Tip: Sets speed up—see [Python Basics](/python/basics).

Final Thoughts: Streak to the Top

LeetCode 128: Longest Consecutive Sequence in Python is an array-chasing thrill. The hash set approach streaks ahead with O(n) speed, while sorting offers a clear alternative. Want more sequence fun? Try LeetCode 53: Maximum Subarray or LeetCode 300: Longest Increasing Subsequence. Ready to count? Head to Solve LeetCode 128 on LeetCode and find that longest streak today!