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,

• 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<n-2; i++)
  {
    for(int j = i+1; j<n-1; 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[i-1]) pq.pop();
    if(!pq.empty() && pq.top()>b[i-1] && 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[i-1]) stk.pop();
    if(!stk.empty() && stk.top()>b[i-1] && 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[i-1]=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

• stk = [4], i = 2, a[i] = 2, b[i-1] = 1

  • stack is not empty and top value is greater then min b[i-1] i.e 1
    so while loop will not execute
  • now we will check conditions from if statement
    !(is stack empty) = !no = yes and
    stk.top()>b[i-1] 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

• s = [4, 2], i = 1, a[i] = 3, b[i-1] = 1

  • now we will check stack and delete top value till the value is smaller values then b[i-1] but here top is 2 and b[i-1]=1 so we will move further
  • now we will check conditions from if statement !(is stack empty) = !no = yes and stk.top()>b[i-1] i.e. (2>1) = yes and a[i]>stk.top() i.e. (3>2) = yes here all conditions are satisfied now we will print yes and return.

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.