<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &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>

auto init = []()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();


class Solution
{
public:
    bool containsDuplicate(vector<int>& nums) // I'd add "const" here if I could
    {                                          // but that's not the interface
        switch(nums.size())
        {
            case 0: return false; //or we could do fallthrough but ¯\_(ツ)_/¯
            case 1: return false;
            case 2: return nums.front()==nums.back();
        }

        auto const begin = nums.begin();
        auto const end = nums.end();

        for(auto cursor = begin+1;cursor != end; cursor+=1)
        {
            if (SortCursor(begin,cursor)) return true;
        }
        return false;
    }

private:
    // preconditions:
    // - range [begin,cursor) is sorted
    // - begin < cursor && cursor < end
    // returns:
    // - true if value of *cursor is in sorted range [begin,cursor)
    // - else false
    bool SortCursor(auto begin, auto cursor) const
    {
        auto sortedEnd = cursor-1;

        if (*sortedEnd == *cursor) return true;

        // worst case for lower_bound occurs when the object is inside/outside
        // the range (that is, the range is sorted or reverse-sorted) so we check
        // for that first.

        //range [begin,cursor] is already sorted and cursor is not a duplicate
        if (*sortedEnd < *cursor) return false;

        auto insertionPoint = (*begin > *cursor)
            ? begin
            : std::lower_bound(begin,cursor,*cursor);

        if(*insertionPoint == *cursor)
            return true;
        
        std::rotate(insertionPoint,cursor,cursor+1);
        return false;
    }
};
59703