# 456. 132 Pattern

## Description

Given an array of 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:

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


Example 2:

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


Example 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 * 105
• -109 <= nums[i] <= 109

## Solutions

• class Solution {
public boolean find132pattern(int[] nums) {
int vk = -(1 << 30);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = nums.length - 1; i >= 0; --i) {
if (nums[i] < vk) {
return true;
}
while (!stk.isEmpty() && stk.peek() < nums[i]) {
vk = stk.pop();
}
stk.push(nums[i]);
}
return false;
}
}

• class Solution {
public:
bool find132pattern(vector<int>& nums) {
int vk = INT_MIN;
stack<int> stk;
for (int i = nums.size() - 1; ~i; --i) {
if (nums[i] < vk) {
return true;
}
while (!stk.empty() && stk.top() < nums[i]) {
vk = stk.top();
stk.pop();
}
stk.push(nums[i]);
}
return false;
}
};

• class Solution:
def find132pattern(self, nums: List[int]) -> bool:
vk = -inf
stk = []
for x in nums[::-1]:
if x < vk:
return True
while stk and stk[-1] < x:
vk = stk.pop()
stk.append(x)
return False


• func find132pattern(nums []int) bool {
vk := -(1 << 30)
stk := []int{}
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] < vk {
return true
}
for len(stk) > 0 && stk[len(stk)-1] < nums[i] {
vk = stk[len(stk)-1]
stk = stk[:len(stk)-1]
}
stk = append(stk, nums[i])
}
return false
}

• function find132pattern(nums: number[]): boolean {
let vk = -Infinity;
const stk: number[] = [];
for (let i = nums.length - 1; i >= 0; --i) {
if (nums[i] < vk) {
return true;
}
while (stk.length && stk[stk.length - 1] < nums[i]) {
vk = stk.pop()!;
}
stk.push(nums[i]);
}
return false;
}


• impl Solution {
pub fn find132pattern(nums: Vec<i32>) -> bool {
let n = nums.len();
let mut vk = i32::MIN;
let mut stk = vec![];
for i in (0..n).rev() {
if nums[i] < vk {
return true;
}
while !stk.is_empty() && stk.last().unwrap() < &nums[i] {
vk = stk.pop().unwrap();
}
stk.push(nums[i]);
}
false
}
}