# 456. 132 Pattern

## LeetCode [**456. 132 Pattern**](https://leetcode-cn.com/problems/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`.*

**Follow up:** The `O(n^2)` is trivial, could you come up with the `O(n logn)` or the `O(n)` solution?

**Example 1**:

```
Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.
```

**Example 2**:

```
Input: [-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 <= 10^4`
* `-10^9 <= nums[i] <= 10^9`

### Tags

Stack

### Solution

基础思想是对于每一个已确定的`nums[j]`，我们先在`j`之前找出最小的`nums[i]`，以保证区间`[nums[i], nums[j]]`足够大，才更有可能找到符合要求的`nums[k]`。

我们可以先构建一个数组`mins`，有`mins[i]=min(nums[:i-1])`。然后倒序遍历`nums`，用一个单调栈维护所有可能的元素`nums[k]`。在循环中，如果有`mins[i] ≥ nums[i]`则跳过本次循环。当栈不为空时，先持续出栈直至栈顶元素不再小于等于`mins[i]`，然后检查这时的栈顶元素是否小于`nums[i]`，如果是则说明找到这个pattern，返回true。循环结束时总是把`nums[i]`入栈。最后返回false。

The basic idea is that, for a particular number `nums[j]`, we can find the smallest `nums[i]` where `i<j`, to maximize the interval `[nums[i], nums[j]]`, so that it is more likely to find a required `nums[k]`.

We first maintain all the smallest `nums[i]` in a `min` array, where requires `mins[i]=min(nums[:i-1])`. Then we traverse `nums` in a descending order and use a stack to keep track of all potential `nums[k]`. In the loop, we continue to check i-1 if `mins[i] ≥ nums[i]`. We always push to `nums[i]` the stack when a loop ends. When the stack is not empty, we keep on popping elements from the stack until `stack[top] ≤ min[k]`. Then check that if the statement `stack[top] < nums[i]` is satisfied we can return a true value. In the end, we return a false value due to no elements in the stack satisfing the 132 pattern.

### Complexity

* Time complexity: $$O(n)$$. You may notice there is a nested for-loop in the second part. But we can note that atmost n elements can be pushed and popped off the stack in total. Thus the second traversal requires only $$O(2n)=O(n)$$ time.
* Space complexity: $$O(n)$$

### Code

```go
func find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	mins, stack := make([]int, len(nums)), make([]int, 0, len(nums))
	mins[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		mins[i] = min(mins[i-1], nums[i])
	}
	for i := len(nums) - 1; i >= 0; i-- {
		if mins[i] >= nums[i] {
			continue
		}
		for len(stack) > 0 && stack[len(stack)-1] <= mins[i] {
			stack = stack[:len(stack)-1]
		}
		if len(stack) > 0 && stack[len(stack)-1] < nums[i] {
			return true
		}
		stack = append(stack, nums[i])
	}
	return false
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```

## Reference

1. <https://leetcode.com/problems/132-pattern/solution/>