Get this book > Problems on Array: For Interviews and Competitive Programming
We will be given an array and we have to find out whether the array has 132 patterns. Given an array a and i, j, k be the index of array then array is said to be in 132 pattern if i < j < k and a[i] < a[k] < a[j].
we will discuss three solutions in detail with implementation and time and space complexity:
 Brute Force [O(N^3) time]
 Using Priority Queue [O(N) time]
 Using Stack [O(N) time]
Brute Force approach
Method:
In this method we will use nested for
loop:

We will create outer
for
loop which will start from 0th index of vector 
Inside that loop we will create outer
for
loop which will start from 1st index of vector. 
Inside second loop we will create another
for
loop which will start from 2nd index 
From this we can assure that index i, j, k will be always i<j<k

This will cover all the triplets we can made using elements of the array

Inside last
for
loop we will check if any triplet will follow a[i]<a[k]<a[j] pattern. If any triplet follow the rule then we will
return true
otherwise we will continue traversing,
 If any triplet follow the rule then we will

At last we will
return false
if the array doesn't have 132 patterns.
Code:
#include<bits/stdc++.h>
using namespace std;
// function for checking 132 patterns in container
void solve(vector<int> &a)
{
int n = a.size();
for(int i=0; i<n2; i++)
{
for(int j = i+1; j<n1; j++)
{
for(int k=j+1; k<n; k++)
{
// checking whether index i, j, k follows 132 pattern or not
if(a[k]<a[j] && a[k]>a[i] && a[j]>a[i])
{
cout<<"Yes"<<endl;
return;
}
}
}
}
cout<<"No"<<endl;
}
int main()
{
// creating vectors
vector<int> a={1, 2, 3, 4}, b={1, 2, 4, 3};
solve(a); // checking 132 pattern in vector a
solve(b); // checking 132 pattern in vector b
return 0;
}
Output:
No
Yes
Time Complexity:
O(n^3) [n = number of elements]
 since we have used nested for loop
Space Complexity:
O(n) [n = number of elements]
 since we haven't created any container except main vector
a
Using Priority Queue approach
Method:

First we will create an vector b in which store value in the index i which will be minimum value till the index

We will create priority queue (minimum heap) for storing elements while traversing reverse of vector

Then initialize for loop which will traverse from last element to first element
 Inside for loop there will be a while loop which will check if the top value of priority queue will be less than the value stored in b in an index less than that index. if the value in top of priority queue is less than minimum value then we will delete that value from priority queue.
 Then we will check whether the top value in priority queue is greater then minimum value and the value stored in current index in array a is greater than the top value from the priority queue, if yes then we will return true otherwise we will continue traversing.

At end we will return false since we haven't found any triplet which is in 132 pattern while traversing.
Code:
#include<bits/stdc++.h>
using namespace std;
// function for checking 132 patterns in container
void solve(vector<int> &a)
{
vector<int> b; //creating vector for storing minimin values
int mn = INT_MAX;
for(int i:a)
{
mn = min(i, mn); b.push_back(mn); // storing minimum values
}
// creating priority queue (min heap)
priority_queue<int, vector<int>, greater<int>> pq;
for(int i=a.size()1; i>0; i)
{
while(!pq.empty() && pq.top()<=b[i1]) pq.pop();
if(!pq.empty() && pq.top()>b[i1] && a[i]>pq.top())
{
cout<<"Yes"<<endl;
return;
}
else pq.push(a[i]);
}
cout<<"No"<<endl;
}
int main()
{
// creating vectors
vector<int> a={1, 2, 3, 4}, b={1, 2, 4, 3};
solve(a); // checking 132 pattern in vector a
solve(b); // checking 132 pattern in vector b
return 0;
}
Output:
No
Yes
Time Complexity:
O(n) [n = number of elements]
 Since we have traversed using for loop only once, and we have used other while loop which will be traversed O(n) times also deleting elements from priority queue will also take O(n) time overall.
Hence overall time Complexity O(n)
Space Complexity:
O(n) [n = number of elements]
 We have created two containers which can be of max n length therefore O(3*n) i.e. O(n).
Using Stack approach
Method:
This is very similar to priority queue method.

First we will create an vector b in which store value in the index i which will be minimum value till the index

We will create stack for storing elements while traversing reverse of vector

Then initialize for loop which will traverse from last element to first element
 Inside for loop there will be a while loop which will check if the top value of stack will be less than the value stored in b in an index less than that index. if the value in top of stack is less than minimum value then we will delete that value from stack.
 Then we will check whether the top value in stack is greater then minimum value and the value stored in current index in array a is greater than the top value from the stack, if yes then we will return true otherwise we will continue traversing.

At end we will return false since we haven't found any triplet which is in 132 pattern while traversing.
Code:
#include<bits/stdc++.h>
using namespace std;
// function for checking 132 patterns in container
void solve(vector<int> &a)
{
vector<int> b; //creating vector for storing minimin values
int mn = INT_MAX;
for(int i:a)
{
mn = min(i, mn); b.push_back(mn); // storing minimum values
}
// creating stack
stack<int> stk;
for(int i = a.size()1; i>0; i)
{
while(!stk.empty() && stk.top() <= b[i1]) stk.pop();
if(!stk.empty() && stk.top()>b[i1] && a[i]>stk.top())
{
cout<<"Yes"<<endl;
return;
}
else stk.push(a[i]);
}
cout<<"No"<<endl;
}
int main()
{
// creating vectors
vector<int> a1={1, 2, 3, 4}, a2={1, 3, 2, 4};
solve(a1); // checking 132 pattern in vector a
solve(a2); // checking 132 pattern in vector b
return 0;
}
Output:
No
Yes
Step by step explaination of using stack example:
Let us understand 132 pattern using Stack.
consider we have our main array
a = {1, 3, 2, 4}
and our minimum array b
we will store the minimum value which will be the minimum value till that index
so our b will be
b = {1, 1, 1, 1}
at starting our stack
will be empty
Inside for
loop

stk = [], i = 3, a[i] = 2, b[i1]=1
 first we will delete the top element from stack using
while
loop but in this example stack is empty so we will proceed further  now we will check conditions from
if
statement
!(is stack empty) = !(yes) = no
, so we will run else part and we will push 4 in Stack
 first we will delete the top element from stack using

stk = [4], i = 2, a[i] = 2, b[i1] = 1
 stack is not empty and top value is greater then min b[i1] i.e 1
sowhile
loop will not execute  now we will check conditions from
if
statement
!(is stack empty) = !no = yes
and
stk.top()>b[i1] i.e. (4>1) = yes
and
a[i]>stk.top() i.e. (2>4) = no
, so we will execute else part we will add 2 to stack
 stack is not empty and top value is greater then min b[i1] i.e 1

s = [4, 2], i = 1, a[i] = 3, b[i1] = 1
 now we will check stack and delete top value till the value is smaller values then b[i1] but here top is 2 and b[i1]=1 so we will move further
 now we will check conditions from
if
statement!(is stack empty) = !no = yes
andstk.top()>b[i1] i.e. (2>1) = yes
anda[i]>stk.top() i.e. (3>2) = yes
here all conditions are satisfied now we will printyes
andreturn
.
Time Complexity
O(n) [n = number of elements]
 Since we have traversed using for loop only once, and we have used other while loop which will be traversed O(n) times also deleting elements from stack will also take O(n) time overall.
Hence overall time Complexity O(n).
Space Complexity:
O(n) [n = number of elements]
 We have created two containers which can be of max n length therefore O(3*n) i.e.
O(n)
.
With this, you have the complete idea of how to solve the 132 Pattern Problem in linear time.