LeetCode 128 - Longest Consecutive Sequence

2026-04-10

medium　array

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [2,20,4,10,3,4,5]

Output: 4

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Constraints:

• 0 <= nums.length <= 1000
• -10^9 <= nums[i] <= 10^9

---

Solution 1:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # Brute Force / Sorting Approach
        # First, sort the array.
        # Second, check if the array is empty. If it is empty, then return 0.
        # Third, initialize two variables to track the lengths:
        # one is the global max length, and the other is the current length.

        # Start iterating and calculate the difference between adjacent elements.
        # If the diff equals 0 (duplicate), then continue.
        # Else if the diff equals 1 (consecutive), increment current_len by 1.
        # Else (sequence broken), we check if the global max length <= current length, and update it if true.
        # Then reset the current length back to the default value (1).

        # In the end, we do one last comparison to check if the final current_len is larger than max_len.
        # Return the result.

        # Time Complexity: O(n log n). Sorting takes O(n log n) time and the iteration takes O(n) time.
        # Space Complexity: O(n) because the 'sorted()' function creates a new list.
        # (Note: It would be O(1) auxiliary space if we used 'nums.sort()' for in-place sorting).

        nums = sorted(nums)
        max_len = 0
        current_len = 1
        if not nums:
            return 0
        for index in range(len(nums) - 1):
            diff = nums[index + 1] - nums[index]
            if diff == 0:
                continue
            elif diff == 1:
                current_len += 1
            else:
                if max_len <= current_len:
                    max_len = current_len
                current_len = 1
        if current_len >= max_len:
            max_len = current_len
        return max_len

Solution 2:

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        # optimal solution
        # First, Check if the array is empty if is empty then return 0
        # Second, turn the nums array into a hash set for O(1) lookup time
        # Third, give a parameter to store the global max length
        # Start iterate the set to find the sequence
        # if the current number minus 1 is in the set, then continue (it is not the start)
        # else it means we find the start of a sequence, give a parameter to record current length
        # use a while loop to check if current number plus 1 is in the set
        # if it is inside, current_len += 1 and update current number
        # in the end of the while loop we compare the global max length, if the global max length <= current length, record current length
        # return the result

        # The time complexity, turn array into set cost O(n) times, and the while loop only run when we find the start of a sequence, so every number is visited at most twice. Overall it cost O(n).
        # The space complexity is O(n) where we use a set to store all the numbers.

        if not nums:
            return 0

        num_set = set(nums)
        max_len = 0

        for num in num_set:
            # Check if this number is the start of a sequence
            if (num - 1) not in num_set:
                current_num = num
                current_len = 1

                # keep finding the next consecutive number
                while (current_num + 1) in num_set:
                    current_num += 1
                    current_len += 1

                # update the global max length
                if max_len <= current_len:
                    max_len = current_len

        return max_len

Takeaway

The naive approach is bottlenecked by sorting at O(n log n). Breaking through to O(n) requires two key shifts in thinking:

1. O(1) lookup with a Hash Set — instead of sorting, convert the array into a set. This turns any membership check from O(log n) into O(1), which is the foundation everything else builds on.

2. Only start counting from sequence heads — to avoid reprocessing the same sequence multiple times, we skip any number where num - 1 exists in the set. If num - 1 is absent, num must be the start of a new sequence. This is the core insight that prevents redundant work.

3. Linear scan from each head — once a head is identified, a while loop walks forward (num + 1, num + 2, ...) accumulating the length, updating the global maximum at the end of each sequence.

The result: each number is visited at most twice across the entire run, keeping the overall time complexity at O(n).