<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:
        # Maintain three dictionaries, one for next values descending, one for next values ascending, and one for seen. Loop through nums list. Only consider unique numbers (check against seen). Cases: 1) Num is next number in both a descending and ascending sequence (in both desc and asc). Combine the sequences, by getting the new total length (desc[num] + asc[num] + 1), adding new next value descending (next num to the left of combined sequence, found by num - asc[num] - 1), adding the next value ascending (next num to the right of combined sequence, found by num + desc[num] + 1), and then removing num from the next values in both desc and asc dictionaries. 2) Num is next number descending, extend sequence in both desc and asc. Add new next value descending with length of extended sequence (desc[num - 1] = desc[num] + 1), find corresponding sequence in asc (asc[num + desc[num] + 1]) and extend it, and then remove num from next value descending. 3) Num is next number ascending, extend sequence in both desc and asc. Add new next value ascending with length of extended sequence (asc[num + 1] = asc[num] + 1), find corresponding sequence in desc (desc[num - asc[num] - 1]) and extend it, and then remove num from next value ascending. 4) Num is not in either dictionary, start new sequence with new next ascending and next descending values. Update seen. Loop through either dictionary (they should be mirrored), and find the longest sequence.
        desc = {}
        asc = {}
        seen = {}
        for num in nums:
            # Only consider unique nums
            if num not in seen:
                # Num is next number in both a descending sequence and an ascending sequence, "join" sequences
                if num in desc and num in asc:
                    total_length = desc[num] + asc[num] + 1
                    # Update descending sequence (next number to the left of combined sequence)
                    lowest_next = num - asc[num] - 1
                    desc[lowest_next] = total_length
                    # Update ascending sequence (next number to the right of combined sequence)
                    highest_next = num + desc[num] + 1
                    asc[highest_next] = total_length
                    # Remove old desc and asc sequences
                    desc.pop(num)
                    asc.pop(num)

                # Num is next number descending, extend sequence in both desc and asc.
                elif num in desc:
                    desc[num - 1] = desc[num] + 1

                    # Get corresponding sequence in asc and extend it
                    asc[num + desc[num] + 1] += 1

                    # Delete desc[num], as it has been extended to a new next number
                    desc.pop(num)

                # Num is next number ascending sequence, extend sequence in both desc and asc.
                elif num in asc:
                    asc[num + 1] = asc[num] + 1

                    # Get corresponding sequence in desc and extend it
                    desc[num - asc[num] - 1] += 1

                    # Delete asc[num], as it has been extended to a new next number
                    asc.pop(num)

                # Num not in either dictionary, start new desc and asc sequence
                else:
                    desc[num - 1] = 1
                    asc[num + 1] = 1

                seen[num] = True
        
        # Loop through either dictionary and find longest sequence (dictionaries should be mirrored)
        longest = 0
        for key in desc.keys():
            if desc[key] > longest:
                longest = desc[key]
        return longest

40570