128. Longest Consecutive Sequence

Medium

---

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

Constraints:

• 0 <= nums.length <= 105

• -109 <= nums[i] <= 109

Solution 1 : New

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        heapq.heapify(nums)
        prev = None
        max_length = 0
        length = 0
        while len(nums):
            num = heappop(nums)
            if prev is None:
                length += 1
            elif prev == num:
                continue
            elif prev+1 != num:
                max_length = max(max_length, length)
                length = 1
            else:
                length += 1
            prev = num
        max_length = max(length, max_length)
        return max_length

Solution 2 : Old

from collections import defaultdict
class Solution:
    # O(n)
    def longestConsecutive(self, nums: List[int]) -> int:
        result = 0
        d = self.get_hashmap(nums)
        for num in nums:
            if (num-1) in d:
                continue
            else:
                count = 1 # One Because this number already counted
                number = num # temp variable
                # Run loop till next number in sequence exists
                while (number+1) in d:
                    number += 1
                    count += 1
                result = max(result,count)
        return result
        
    def get_hashmap(self, nums):
        d = defaultdict(int)
        for num in nums:
            d[num] = d[num] + 1
        return d

    # O(nlogn)
    def longestConsecutiveOld(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        nums.sort()
        index = 0
        maxLength = -1
        count = 1
        # print('Sorted', nums)
        while index < len(nums)-1:
            if nums[index+1] == nums[index]:
                index += 1
            elif nums[index+1] == nums[index]+1:
                count += 1
                index += 1
            else:
                maxLength = max(maxLength, count)
                count = 1
                index += 1
        maxLength = max(maxLength, count)
        return maxLength