456. 132 Pattern

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size() < 3)
            return false;

        vector<int> mins(nums.begin(), nums.end());
        set<int> s;
        s.insert(nums.back());
        for(int i = 1; i < mins.size(); i++) {
            mins[i] = min(mins[i], mins[i - 1]);
        }
        set<int>::iterator it = s.begin();
        for(int i = nums.size() - 2; i > 0; i--) {
            s.insert(nums[i]);
            if(mins[i] >= nums[i])
                continue;
            
            it = s.lower_bound(mins[i] + 1);
            
            if(it != s.end() and *it < nums[i] and *it > mins[i])
                return true;
        }
        return false;
    }
};

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size() < 3)
            return false;
        
        vector<int> mins(nums.begin(), nums.end());
        for(int i = 1; i < mins.size(); i++) {
            mins[i] = min(mins[i], mins[i - 1]);
        }
        for(int j = (int)nums.size() - 1, k = (int)nums.size(); j > 0; j--) {
            if(mins[j] >= nums[j]) {
                continue;
            }
            
            while(k < (int)nums.size() && nums[k] <= mins[j])
                ++k;
            if(k < nums.size() && nums[k] < nums[j])
                return true;
            
            nums[--k] = nums[j];
        }
        return false;
    }
};