0128.Longest Consecutive Sequence

• Link: 128. Longest Consecutive Sequence - Medium
• Track: NeetCode150, Amazon

Question

• Example 1:
  • Input: nums = [100,4,200,1,3,2]
  • Output: 4
  • Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Restate

• Given integer array of nums
• Find the longest consecutive elements sequence
• Return the length of longest consecutive sequence

Edge Case

• nums = [] → 0
• Duplicates: [1,2,2,3] → longest is 3 (1,2,3)
• Negative numbers: [-2,-1,0,1] → 4
• All same: [7,7,7] → 1

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	HashSet	$O(n)$	$O(n)$

Method 1 - HashSet

Approach

• Put all numbers into a set s for O(1) average membership checks.
• For each num in num_set:
  • If num-1 exists, skip (not a start).
  • Otherwise, expand num, num+1, num+2, ... while in num_set.
• Track max length

Complexity

• Time Complexity: $O(n)$
  • Even though there is a for loop and a while loop, each number is visited at most once
• Space Complexity: $O(n)$

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums) # O(n)
        res = 0
        for val in num_set:
            if val - 1 in num_set:
                continue
            
            length = 0
            cur = val
            while cur in num_set:
                length += 1
                cur += 1
            
            res = max(res, length)
 
        return res

---

Common Mistake

• Time complexity is $O(n)$
• Even though a set is unordered, it is still iterable, and the iteration order is not guaranteed.