Longest Consecutive Sequence

Problem

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.

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 <= 10:sup:`5`

• -10:sup:`9`<= nums[i] <= 10:sup:`9`

Pattern

Array, Hash Table, Union-Find

Approaches

Hash Set

Code

def longestConsecutive(nums: list[int]) -> int:
    """Return the length of the longest consecutive elements sequence."""
    if not nums:
        return 0

    num_set = set(nums)

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

    return longest

Test

>>> from longest_consecutive_sequence__hash_set import longestConsecutive
>>> longestConsecutive([100, 4, 200, 1, 3, 2])
4
>>> longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])
9

longest_consecutive_sequence__hash_set.longestConsecutive(nums: list[int]) → int

Return the length of the longest consecutive elements sequence.

Hash Map

Code

from collections import defaultdict


def longestConsecutive(nums: list[int]) -> int:
    """Return the length of the longest consecutive elements sequence."""
    mp = defaultdict(int)
    res = 0

    for num in nums:
        if not mp[num]:
            mp[num] = mp[num - 1] + mp[num + 1] + 1
            mp[num - mp[num - 1]] = mp[num]
            mp[num + mp[num + 1]] = mp[num]
            res = max(res, mp[num])
    return res

Test

>>> from longest_consecutive_sequence__hash_map import longestConsecutive
>>> longestConsecutive([100, 4, 200, 1, 3, 2])
4
>>> longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])
9

longest_consecutive_sequence__hash_map.longestConsecutive(nums: list[int]) → int

Return the length of the longest consecutive elements sequence.