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.
- 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.
- We keep track of the maximum of such s3, which is always the most recently popped number from the stack.
- 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;
}
};