:orphan:

Longest Consecutive Sequence
============================

.. highlight:: none

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```

.. highlight:: python

Pattern
-------
Array, Hash Table, Union-Find

Approaches
----------

.. tab-set::

    .. tab-item:: Hash Set

        **Code**

        .. literalinclude:: ../problems/medium/longest-consecutive-sequence/longest_consecutive_sequence__hash_set.py
            :language: python
            :lines: 9-

        **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

        .. autofunction:: longest_consecutive_sequence__hash_set.longestConsecutive