<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:
        # keep track of numbers in array through a heap
        numbers_available = list(nums)
        heapq.heapify(numbers_available)
        
        # build consecutive sequence if next num is in heap, otherwise start new sequence
        longest_sequence = 0

        # pop elements from heap until heap is empty
        prev = float('inf')
        current_sequence = 0
        while numbers_available:
            curr_num = heapq.heappop(numbers_available)
            if curr_num == prev:
                continue
            # current num is part of old sequence
            if self.isConsecutive(prev, curr_num):
                current_sequence += 1
            # current num is start of new sequence
            else:
                longest_sequence = max(longest_sequence, current_sequence)
                current_sequence = 1
            prev = curr_num

        # check if final sequence is greater than previous longest sequence
        longest_sequence = max(longest_sequence, current_sequence)
        return longest_sequence
    
    def isConsecutive(self, prev, curr):
        return curr-1 == prev
30850