This question is asking us to find “132” pattern in the array. This reminds me of the stack-sortable permutation, which was introduced by Knuth. Please read the detailed explanation at the Wikipedia first.
Stack-sortable permutations are the sequence of numbers that are sortable using a stack and thus it should not contain “231” pattern. Once you read the article, you can easily understand why the “231” pattern prevents it from being sorted.
This question is very similar with the problem that identifies the sequence of number is stack-sortable or not.
So if we reverse the array and find if its sortable or not [ this will help us to find whether the reversed array has a “231” pattern or not , and in turn “132” pattern in the original array ]
So i coded this out, but unfortunately i am facing WA in some test cases.
MY CODE:
// I am checking if the array is sorted or not, based on the wiki page code..
class Solution {
public:
bool find132pattern(vector<int>& nums) {
stack<int> s;
reverse(nums.begin(),nums.end());
vector<int> a;
for(auto x:nums){
while(!s.empty() and x>=s.top())
{a.push_back(s.top());
s.pop();
}
s.push(x);
}
while(!s.empty()){
a.push_back(s.top());
s.pop();
}
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(nums[i]!=a[i]) return 1;
}
return 0;
}
};
EDIT: So it turns out i missed some cases where the array looks like [1,3,3] which is stack sortable but not of the pattern 132, how can i edit my existing sol to cover this up
There is a simple way to solve this in O(n\log{n}) with the data structure “set”.
Iterate j from 1 to n. Maintain the set of all elements to the right and left to a_j. Check if the smallest element less than a_j in the left set is lesser than the largest element less than a_j in the right set. If it is, then there is a 1 \ 3\ 2, else check the next j.