<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 {
public:
    int longestConsecutive(const std::vector<int>& nums) {
        if (nums.empty())
            return 0;

        auto [minIt, maxIt] = std::minmax_element(nums.begin(), nums.end());
        const int minV = *minIt;
        const int maxV = *maxIt;

        constexpr size_t SpanWidth = 1 << 21;
        std::bitset<SpanWidth> bs;

        std::vector<std::pair<int, int>> sequences;

        int maxLength = 1;
        int spanBegin = minV;
        while (spanBegin <= maxV)
        {
            const int spanEnd = spanBegin + SpanWidth - 1;

            bs.reset();

            for (int n : nums)
            {
                const int offset = n - spanBegin;
                if (offset >= 0 && offset < SpanWidth)
                    bs.set(offset);
            }

            if (bs.any())
            {
                int sqBegin = 0;
                while (sqBegin < SpanWidth)
                {
                    while (sqBegin < SpanWidth && !bs.test(sqBegin))
                        ++sqBegin;

                    int sqEnd = sqBegin + 1;
                    while (sqEnd < SpanWidth && bs.test(sqEnd))
                        ++sqEnd;
                    const int sqLen = sqEnd - sqBegin;

                    if (sqLen > 1)
                    {
                        maxLength = std::max(maxLength, sqLen);
                        if (sqBegin == 0 || sqEnd == SpanWidth)
                            sequences.emplace_back(spanBegin + sqBegin, spanBegin + sqEnd - 1);
                    }

                    sqBegin = sqEnd;
                }
            }

            spanBegin += SpanWidth;
        }

        if (sequences.size() > 1)
        {
            for (size_t sqNum = sequences.size() - 1; sqNum > 0; --sqNum)
            {
                auto& curSq = sequences[sqNum];
                auto& prevSq = sequences[sqNum - 1];
                if (curSq.first == prevSq.second + 1)
                {
                    prevSq.second = curSq.second;
                    maxLength = std::max(maxLength, prevSq.second - prevSq.first + 1);
                }
            }
        }

        return maxLength;
    }
};
17030