132 Pattern -- LeetCode 456

[Question]

Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

[Analysis]
Use a Set (binary search tree) to collect uphill ranges from the beginning of the array. For the next number in array, use Binary Search to the the range that might be a 132 pattern. If not, the number will form a new range and be put into the Set. The trick to form a range to use a variable 'low' to track the lowest value so far in the array.

Another solution is to think about the 132 pattern in back-forward, which is 231 pattern. It is much simpler because there is no need to record the ranges. As long as we '23' pattern is tracked, largest '2' is recorded and the new coming number is smaller than '2', the return is true. This time complexity is O(N).

[Solution]
//-- sol.#1: Binary Search --
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int low = INT_MAX;
        auto comp = []( pair<int,int> a, pair<int,int> b ) { return a.second < b.second;};
        set<pair<int,int>, decltype(comp)> pairs (comp);
     
        for(auto n: nums) {
            if (!pairs.empty()) {
                auto it = pairs.upper_bound({n,n});
                if (it!=pairs.end() && it->first<n && n<it->second)
                    return true;
                pairs.erase( pairs.begin(), it );
            }
            low = min(low,n);
            if (low< n) pairs.insert( {low, n});
        }
        return false;
    }
};

//-- sol. #2 Stack --

class Solution {

public:

    bool find132pattern(vector<int>& nums) {

        if (nums.size()<3) return false;

        

        stack<int> st; 

        int third = INT_MIN;

        for (int i= nums.size()-1; i>=0; i--) {

            if (nums[i] < third) return true;

            else {

                while (!st.empty() && nums[i]>st.top()) {

                    third = st.top(); st.pop();

                }

            }

            st.push(nums[i]);

        }

        return false;

    }

};