# 132 Pattern Problem

## Description

LeetCode Problem 456.

Given an arrayof n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

``````1
2
3
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
``````

Example 2:

``````1
2
3
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
``````

Example 3:

``````1
2
3
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
``````

Constraints:

• n == nums.length
• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

## Sample C++ Code

The problem is to find a subsequence (s1, s2, s3) such that s1 < s3 < s2.

We can start from the end, and search for pair (s2, s3) such that s2 > s3. We keep track of highest value of s3 for each valid (s2 > s3) pair while searching for a valid s1 candidate to the left. Once we encounter any number on the left that is smaller than the largest s3 we have seen so far, we know we find a valid subsequence.

We use a stack to keep track of the largest valid s3 value.

1. As we scan from right to left, each time we have a number greater than the top of the stack, it is a potential s2. We then pop out all the numbers that are smaller than this number. The numbers that are popped out are candidates for s3.
2. We keep track of the maximum of such s3, which is always the most recently popped number from the stack.
3. Once we encounter any number smaller than s3, we find a s1. Then we find a valid subsequence s1, s2, s3. (As the algorithm ensures that for the s3 we store, there is a valid s2 for it. Thus, if we find a number that is smaller than the stored s3, we are done. Based on this reason, we only need to store the max s3 we found.)

Example:

``````1
2
3
4
5
i = 6, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = None, Stack = Empty
i = 5, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 7, S3 candidate = None, Stack = [9]
i = 4, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 10, S3 candidate = None, Stack = [9,7]
i = 3, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = 9, Stack = [10]
i = 2, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 8, S3 candidate = 9, Stack = [10,9] We have 8<9, sequence (8,10,9) found!
``````

Solution:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool find132pattern(vector<int>& nums) {
int s3 = INT_MIN;
stack<int> st;
for(int i = nums.size()-1; i >= 0; i --){
if (nums[i] < s3)
return true;
else
while (!st.empty() && nums[i] > st.top()) {
s3 = st.top();
st.pop();
}
st.push(nums[i]);
}
return false;
}
};
``````