<p>Given an array of <code>n</code> integers <code>nums</code>, a <strong>132 pattern</strong> is a subsequence of three integers <code>nums[i]</code>, <code>nums[j]</code> and <code>nums[k]</code> such that <code>i &lt; j &lt; k</code> and <code>nums[i] &lt; nums[k] &lt; nums[j]</code>.</p>

<p>Return <code>true</code><em> if there is a <strong>132 pattern</strong> in </em><code>nums</code><em>, otherwise, return </em><code>false</code><em>.</em></p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no 132 pattern in the sequence.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,1,4,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> There is a 132 pattern in the sequence: [1, 4, 2].
</pre>

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

<pre>
<strong>Input:</strong> nums = [-1,3,2,0]
<strong>Output:</strong> true
<strong>Explanation:</strong> There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
</pre>

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

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 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:
    void insertpair( vector<pair<int,int>> & vp, int mini, int maxj )
    {
        for( auto & elt : vp )
        {
            if( mini >= elt.first && maxj <= elt.second )
                return;     // completely contained within this one
            if( mini <= elt.first && maxj >= elt.second )
            {
                elt.first = mini;
                elt.second = maxj;
                return;     // completely contained within this one
            }
        }
        vp.push_back( make_pair( mini, maxj ) );
    }
    bool matches( vector<pair<int,int>> & vp, int kv )
    {
        for( auto & elt : vp )
        {
            if( kv > elt.first && kv < elt.second )
                return( true );
        }
        return( false );
    }
    bool find132pattern(vector<int>& nums) {
        // for i,j,k, successively increasing indexes, we want
        // nums[i] < nums[k] < nums[j]
        // so we need a min, then max, followed by an interior
        int mini = nums[0];
        int maxj = INT_MIN;
        vector<pair<int,int>> vp;
        for( int i = 1; i < nums.size(); ++i )
        {
            int num = nums[i];
            //cout << "num=" << num << ", min=" << mini << ", max=" << maxj << endl;
            if( maxj > mini && num > mini && num < maxj )
                return( true );
            if( num < mini )
            {
                if( maxj > mini + 1 )
                {   // this means we have a pair that might find a later match
                    insertpair( vp, mini, maxj );
                }
                // Track new min going forward
                mini = num;
                maxj = INT_MIN;
            }
            else if( num > maxj )
            {
                maxj = num;
            }
            if( !vp.empty() && matches( vp, num ) )
                return( true );
        }
        return( false );
    }
};
67201