---
tags: data_structure_python
---

# Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

# Solution 1

- O(n³)
- Outer loop: O(n)
- `curr_num` gets incremented n times (worse case)
- check `curr_num + 1 in nums` is O(n)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        maxCount = 0
        for num in nums:
            curr_num = num
            count = 1
            
            while curr_num + 1 in nums:
                curr_num += 1
                count += 1
            
            maxCount = max(maxCount, count)
        
        return maxCount

# Solution 2

- O(logn) time complexity

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        sorted_nums = sorted(nums)
        maxCount, count = 0, 1
        
        for i in range(len(sorted_nums)-1):
            if sorted_nums[i] != sorted_nums[i+1]:
                if abs(sorted_nums[i] - sorted_nums[i+1]) == 1:
                    count += 1
                else:
                    maxCount = max(maxCount, count)
                    count = 1

        return max(maxCount, count)

# Solution 3

- O(n) time complexity.
- Use a set for O(1) lookup
- Only compute longest element sequence for the smallest number of the sequence (that's why the complexity is not O(n²) but O(n))

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        
        maxCount = 0
        nums_set =  set(nums)
        
        for num in nums:
            
            if num - 1 in nums_set:
                # no need for current num to start its own sequence
                # because it is already part of a longest consecutive
                # elements sequence
                continue
            else:
                curr_num = num
                count = 1

                while curr_num + 1 in nums_set:
                    curr_num += 1
                    count += 1
            
                maxCount = max(maxCount, count)
        
        return maxCount