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

from collections import defaultdict


def longestConsecutive(nums: list[int]) -> int:
    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_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