Leetcode 456 Solution

This article provides solution to leetcode question 456 (132-pattern)
Categories:
Tags:
Access this page by simply typing in "lcs 456" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/132-pattern

Solution

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        std::set<int, std::greater<int> > m;
        int curr_min = INT_MAX;
        vector<int> a(nums.size());

        for (int i = nums.size() - 1; i >= 0; i--)
        {
            auto it = m.upper_bound(nums[i]);

            if (it == m.end())
                a[i] = INT_MAX;
            else
                a[i] = *it;

            m.insert(nums[i]);
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (curr_min >= nums[i])
                curr_min = nums[i];
            else if (a[i] != INT_MAX && a[i] > curr_min)
                return true;
        }

        return false;
    }
};