Stacks: Check if the given pattern exist in the array

Problem Statement:

You are given an array, you need to find 3 integers, such that i < j < k and nums[i] < nums[k] < nums[j]

Example

Input: nums = [3,1,4,2]
Output: True

The sequence is: [1, 4, 2]

Solution

We will use stack for the solution.

Basic Idea:

The highest element will remain in stack.
The 2nd largest will remain in temp variable “second”, then if we find the element that is smaller than the second, then we will return true.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 

using namespace std;


bool find_132_pattern(vector<int>& nums) 
{
    
    stack <int> stack;
    int second =  -2147483648;
    for (int i = nums.size() - 1; i >= 0; i--) {
        if (nums [i] < second)
            return true;
        while (stack.size() >0 && nums [i] > stack.top()){
            second = stack.top ();
            stack.pop();
        }
            
        stack.push (nums [i]);
    }
    return false;
    
}
int main()
{
   vector<int> v = {3,1,4,2};

    if(find_132_pattern(v))
    {
        cout<<"True"<<endl;
    } else {
        cout<<"False"<<endl;
    }

    return 0;
}

Output:

True

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *