<p>Given an unsorted array of integers <code>nums</code>, return <em>the length of the longest consecutive elements sequence.</em></p>

<p>You must write an algorithm that runs in&nbsp;<code>O(n)</code>&nbsp;time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [100,4,200,1,3,2]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest consecutive elements sequence is <code>[1, 2, 3, 4]</code>. Therefore its length is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,3,7,2,5,8,4,6,0,1]
<strong>Output:</strong> 9
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        # using hash set and seen set: O(n)
        nums_set = set(nums)
        seen_set = set()
        longest = 0
        for n in nums_set:
            if n in seen_set:
                continue
            seen_set.add(n)
            count = 1
            c = n
            while c + 1 in nums_set:
                seen_set.add(c + 1)
                count += 1
                c += 1
            if count > longest:
                longest = count
        return longest

        # # sorting solution: O(n * log(n))
        # if not nums:
        #     return 0
        # if len(nums) == 1:
        #     return 1
        # nums_set = set(nums)
        # nums = list(nums_set)
        # nums.sort()
        # longest = 1
        # count = 1
        # prev = nums[0]
        # for i in range(1, len(nums)):
        #     if prev == nums[i] - 1:
        #         count += 1
        #         if count > longest:
        #             longest = count
        #     else:
        #         count = 1
        #     prev = nums[i]
        # return longest

        # # naive solution - memory limit exceeded
        # if not nums:
        #     return 0
        # if len(nums) == 1:
        #     return 1
        # # find min and max value O(n)
        # low = min(nums)
        # high = max(nums)
        # t = [False] * (high - low + 1)  # e.g. 3-1=2 but need 3 for 1,2,3
        # for n in nums:
        #     t[n - low] = True
        # longest = 0
        # count = 0
        # for i in t:
        #     if i:
        #         count += 1
        #         if count > longest:
        #             longest = count
        #     else:
        #         count = 0
        # return longest

36610