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

#include <unordered_map>

using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> runs;
        int max_length = 0;
        for(auto& elem: nums){
            if(runs.find(elem) == runs.end()){
                if(runs.find(elem-1) == runs.end() && runs.find(elem+1) == runs.end()){
                    runs[elem] = elem;
                    if(1 > max_length) max_length = 1;
                }
                else{
                    if(runs.find(elem-1)!=runs.end() && runs.find(elem+1)!=runs.end()){
                        if(elem > runs[elem-1] && elem < runs[elem+1]){
                            int ogplus = runs[elem+1];
                            int ogminus = runs[elem-1];
                            if(ogplus - ogminus + 1 > max_length){
                                max_length = ogplus - ogminus + 1;
                            }
                            runs[ogminus] = ogplus;
                            runs[ogplus] = ogminus; 
                            /*
                            cout << runs[elem+1] - runs[elem-1] + 1 << endl;
                            for(auto i: runs){
                                cout << i.first << ": " << i.second << endl;
                            }
                            cout << "-------" << endl;
                            */
                            if(ogplus!=elem+1) runs.erase(elem+1);
                            if(ogminus!=elem-1) runs.erase(elem-1);
                        }
                    }
                    else if(runs.find(elem-1)!=runs.end()){
                        if(runs[elem-1] <= elem-1){
                            runs[elem] = runs[elem-1];
                            runs[runs[elem-1]] = elem;
                            if(runs[elem]!= elem-1){
                                runs.erase(elem-1);
                            }
                            if(elem-runs[elem] +1 > max_length){
                                max_length = elem-runs[elem] +1;
                            }
                        }
                    }
                    else{
                        //runs[elem+1] is in the hashmap
                        if(runs[elem+1] >= elem+1){
                            runs[elem] = runs[elem+1];
                            runs[runs[elem+1]] = elem;
                            if(runs[elem]!= elem + 1){
                                runs.erase(elem+1);
                            }
                            if(runs[elem] - elem +1 > max_length){
                                max_length = runs[elem] - elem +1;
                            }
                        }
                    }
                }
            }
            /*cout<< "number: " << elem << endl;
            for(auto i: runs){
                cout << i.first << ": " << i.second << endl;
            }
            cout << "--------------- " << endl;
            */
        }
    return max_length;

    }
};
66406