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