LC 128 - Longest Consecutive Sequence

Question

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.

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.

Example 2:

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Links

Question here and solution here

Solution

concept

The easiest way to do this is to sort the array first and then count the streak. However since sorting is typically $O(n \log n)$ so it might be fit the question description (but the solution are still accepted)

We can put all numbers in to a set. We then check if a number - 1 is in the set. If it is not in the set then we know this is the start of the sequence. We can then check subsequent number if it is in the set.

code

class Solution:
	"""
	sort the array first
	"""
    def longestConsecutive(self, nums: List[int]) -> int:
        nums.sort()
        streak = 1
        ans = 1
        for i in range(len(nums) - 1):
            if nums[i] == nums[i+1]:
                continue
            elif nums[i] + 1 == nums[i + 1]:
                streak += 1
                ans = max(ans, streak)
            else:
                streak = 1
        return ans if nums else 0

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for num in numSet:
            if (num - 1) not in numSet:
                length = 1
                while (num + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

Complexity

time: $O(n)$
space: $O(n)$