9. Longest Consecutive Sequence

Problem

Given an array of integers nums, return the length of the longest consecutive sequence of elements. A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [2,20,4,10,3,4,5]
 
Output: 4

Copy

Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:

Input: nums = [0,3,2,5,4,6,1,1]
 
Output: 7

Copy

Constraints:

• 0 <= nums.length <= 1000
• -10^9 <= nums[i] <= 10^9

---

Solutions

1. Sorting

Time Complexity: $O(n\log n)$ | Space Complexity: $O(1)$

The solution involves sorting the array and iterating through its elements, counting the maximum streak of consecutive elements. To handle duplicates, we use continue if the current element is the same as the previous one.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
 
        if len(nums) == 0:
            return 0
 
        nums.sort()
 
        max_counter = 1
        counter = 1
 
        for i in range(1, len(nums)):
            cur, prev = nums[i], nums[i-1]
            if cur == prev: continue
            if prev + 1 == cur:
                counter += 1
            else:
                counter = 1
            max_counter = max(counter, max_counter)
 
        return max(max_counter, counter)
 

---

🏆 2. Hashing

Time Complexity: $O(n)$ | Space Complexity: $O(1)$

To solve the problem with the required time complexity of $O(n)$, we can utilize a set. Once we build the set based on the given array, we iterate through its elements. If the element immediately preceding the current element (element - 1) is in the set, we skip the iteration to avoid double-counting (otherwise, it would not be $O(n)$. Then, while the next potential element (element + 1) is in the set, we increment the counter.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
 
        if len(nums) == 0:
            return 0
 
        memo = set(nums)
 
        max_counter = 0
        for element in memo:
            if element - 1 in memo: continue
            counter = 1
            while element + 1 in memo:
                element += 1
                counter += 1
            max_counter = max(max_counter, counter)    
 
        return max(max_counter, counter)