O(nlogn) Solution Using STL Multimap


  • 2
    H

    class Solution {
    public:
    bool find132pattern(vector<int>& nums)
    {
    multiset<int> left;
    multiset<int> right;

        for(auto it: nums)
            right.insert(it);
        
        for(auto it: nums)
        {
            if(left.size() > 0 and right.size() > 0)
            {    
                int lo = *left.begin();
                auto it1 = right.lower_bound(it);
                if(it1 != right.begin())
                {
                    it1--;
                    int hi = *it1;
                    if(lo < it and hi < it and hi > lo)
                    return 1;
                }
            }
            
            left.insert(it);
            auto it2 = right.find(it);
            right.erase(it2);
        }
        
        return 0;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.