0128. Longest Consecutive Sequence

Problem Category:: Array, Set Neetcode Category:: Arrays and Hashing

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

Given an unsorted array of integers nums, return _the length of the longest consecutive elements sequence.

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

Thoughts

• $O(n)$ so sorting is unlikely, probably have to use a dict based method with either Dictionary ADT or Set ADT
• If we can’t avoid a nested loop, then we must find a way

Optimal

Sets and avoiding repetition when sequence building

Alter the brute force algorithm to use the Dictionary based Set ADT for constant lookup, and then thus avoid repetition when building sequences

Python full solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_streak = 0
        # Use set which is implemented by a dict
        num_set = set(nums)
        
        # O(n)
        for num in num_set:
            current_num = num
            current_streak = 1
            # Ensure the preceding number is not already in the set to avoid repetition - if not then it will be a unique sequence
            if (num - 1) not in num_set: #O(1) lookup
                while current_num + 1 in num_set:
                    current_streak += 1
                    current_num += 1
                max_streak = max(max_streak, current_streak)
        
        return max_streak

Python shorter solution

class Solution:
    def longestConsecutive(self, nums):
        nums = set(nums)
        max_streak = 0
        for num in nums:
            if num - 1 not in nums:
                curr_tail = num + 1 # current end of consec seq.
                while curr_tail in nums:
                    curr_tail += 1
                max_streak = max(max_streak, curr_tail - num)
        return max_streak

Time complexity: $O(n)$

• The inner while loop only runs $O(n)$ time throughout the entire algorithm as it only passes once through each unique “increasing sequence”
• Conversion to set $O(n)$ Space complexity: $O(n)$ to store the set

Failed solutions

Brute force

Python solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_streak = 0
        # O(n)
        for num in nums:
            current_num = num
            current_streak = 1
            # O(n) each time, max n times -> O(n^2)
            while current_num + 1 in nums:
                current_streak += 1
                current_num += 1
 
            max_streak = max(max_streak, current_streak)
        return max_streak

• Loop through the list, try to build a streak by searching for the next number each time
• $O(n^3)$ time complexity, $O(1)$ space complexity

Sorting

Python solution

class Solution:
    def longestConsecutive(self, nums):
        if not nums:
            return 0
 
        nums.sort()
 
        longest_streak = 1
        current_streak = 1
 
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                if nums[i] == nums[i-1]+1:
                    current_streak += 1
                else:
                    longest_streak = max(longest_streak, current_streak)
                    current_streak = 1
 
        return max(longest_streak, current_streak)