O(NlogN) time O(N) memory Balanced BST solution, compact code


  • 0
    N
    class Solution {
    public:
        bool find132pattern(vector<int>& nums) {
            if (nums.size() < 3) {
                return false;
            }
            typedef std::multiset<int>::iterator TIt;
            std::multiset<int> s;
            vector<TIt> v;
            for (int i = 2; i < nums.size(); ++i) {
                auto it = s.insert(nums[i]);
                v.push_back(it);
            }
            
            int cMin = nums[0];
            for (int i = 1; i + 1 < nums.size(); ++i) {
                if (nums[i] < cMin) {
                    cMin = nums[i];
                } else if (nums[i] > cMin) {
                    auto it1 = s.upper_bound(cMin);
                    auto it2 = s.lower_bound(nums[i]);
                    if (it1 != s.end() && (it2--) != it1) {
                        return true;
                    }
                }
                s.erase(v[i - 1]);
            }
            return false;
        }
    };
    

Log in to reply
 

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