<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:
        if not nums:
            return 0
        start_number_to_end_number = {}
        end_number_to_start_number = {}
        nums = set(nums)
        for n in nums:
            # print(n)
            if n+1 in start_number_to_end_number and n-1 in end_number_to_start_number:
                # That means this exists in two sequences that we need to merge
                # print("Merging")
                start_number = end_number_to_start_number[n-1]
                end_number = start_number_to_end_number[n+1]
                start_number_to_end_number[start_number] = end_number
                end_number_to_start_number[end_number] = start_number
            elif n+1 in start_number_to_end_number:
                # print("n+1 was a start number")
                start_number = n
                end_number = start_number_to_end_number[n+1]
                start_number_to_end_number[start_number] = end_number
                del start_number_to_end_number[n+1]
                end_number_to_start_number[end_number] = start_number
            elif n-1 in end_number_to_start_number:
                # print("n-1 was an end number")
                end_number = n
                start_number = end_number_to_start_number[n-1]
                end_number_to_start_number[end_number] = start_number
                del end_number_to_start_number[n-1]
                start_number_to_end_number[start_number] = end_number
            else:
                # print("n not found, adding")
                start_number_to_end_number[n] = n
                end_number_to_start_number[n] = n
        #     print(start_number_to_end_number)
        #     print(end_number_to_start_number)
        # print(start_number_to_end_number)
        # print(end_number_to_start_number)
        # merge them
        # for k, v in list(start_number_to_end_number.items()):
        #     while v in start_number_to_end_number:
        #         start_number_to_end_number[k] = start_number_to_end_number[v]
        #         if v != k:
        #             del start_number_to_end_number[v]
        #         else:
        #             break
        #         v = start_number_to_end_number[k]
        # print(start_number_to_end_number)
        return max([v - k for k, v in start_number_to_end_number.items()]) + 1

37870