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