# 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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/456.-132-pattern.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.