Leetcode 456 Solution

This article provides solution to leetcode question 456 (132-pattern)

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; } };