# Evolve from brute force to optimal

1. O(n^3), try all triplets
``````    bool find132pattern(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n-2;i++)
for(int j=i+1;j<n-1;j++) {
if(nums[j]-nums[i]<=1) continue;
for(int k=j+1;k<n;k++)
if(nums[i]<nums[k] && nums[k]<nums[j]) return 1;
}
return 0;
}
``````
1. O(n^2), 3 and 2 can be tried in one pass. For each 1, we cache the current max as 3.
``````    bool find132pattern(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n-2;i++) {
int three = nums[i];
for(int j=i+1;j<n;j++)
if(nums[j] > three) three = nums[j];
else if(nums[j] < three && nums[i]<nums[j]) return 1;
}
return 0;
}
``````
1. O(nlongn), instead of trying in the order of i, j, k as above, we can try each j and see if we have a valid i on the left and a valid k on the right. When checking for a valid k, we only need to check the next number of aj in descending order. And bst fits here.
``````    bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(n<3) return 0;
int mi = nums[0];
vector<int> left(n);
for(int i=1;i<n-1;i++) {
left[i] = mi;
mi = min(nums[i],mi);
}
set<int,greater<int>> bst{nums.back()};
for(int i=n-1;i>0;i--) {
if(nums[i] > left[i] + 1) {
auto right = bst.upper_bound(nums[i]);
if (right != bst.end() && *right > left[i]) return 1;
}
bst.insert(nums[i]);
}
return 0;
}
``````
1. O(n), similar to #3, we can use a stack to cache all the numbers on the right of j and checking can be done in constant time.
When visiting nums from end to beginning, left[j] increases, so it is sufficient to check if a number is a valid k the first time we see a j larger than it. The numbers in the stack is always ascending from top to bottom.
``````    bool find132pattern(vector<int>& nums) {
int n = nums.size();
if(n<3) return 0;
int mi = nums[0];
vector<int> left(n);
for(int i=1;i<n-1;i++) {
left[i] = mi;
mi = min(nums[i],mi);
}
stack<int> stk({nums.back()});
for(int i=n-1;i>0;i--) {
if(nums[i] > left[i] + 1)
while(!stk.empty() && nums[i]>stk.top()) {
if (stk.top() > left[i]) return 1;
stk.pop();
}
stk.push(nums[i]);
}
return 0;
}
``````

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