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

• 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

結語：

在初步解題時，直覺的暴力解法會受限於「排序 (Sorting)」所帶來的 O(nlogn) 效能瓶頸。 為了將時間複雜度降至 O(n)，本題的突破口在於資料結構的轉換與核心邏輯的優化：

1. Hash Set 的 O(1) 查找：放棄傳統排序，將陣列轉換為 Set，利用其 Hash Table 的特性，將數值搜尋的時間複雜度降至 O(1)。
2. 定位「序列起點 (Sequence Head)」：為了避免重複計算，我們只需針對每段連續序列的「開頭」進行遍歷。判斷邏輯如下：若 num - 1 不存在於 Set 中，即可斷定 num 就是該段序列的起點。
3. 單向遞增計算：一旦確認為起點，便利用 while 迴圈向上尋找 (num + 1, num + 2...) 並累加長度，同時動態更新全局的最長紀錄。