# LeetCode 456. 132 Pattern

06 Sep 2018## Description:

Given a sequence of \(n\) integers \(a_1, a_2, …, a_n\), a 132 pattern is a subsequence \(a_i\), \(a_j\), \(a_k\) such that \(i < j < k\) and \(a_i < a_k < a_j\). Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

## Example:

input:

`[1,2,3,4]`

output:

`False`

explanation:

There is no 132 pattern in the sequence.

input:

`[3,1,4,2]`

output:

`True`

explanation:

There is a 132 pattern in the sequence:

`[1, 4, 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]`

.

## Note:

\(n\) will be less than 15,000.

## Solution:

```
class Solution:
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) < 3:
return False
minLeft = [None] * len(nums)
maxRight = [None] * len(nums)
leftMin = nums[0]
for i in range(0, len(nums)):
if nums[i] < leftMin:
leftMin = nums[i]
minLeft[i] = leftMin
rightHelper = []
for i in range(len(nums) - 1, -1, -1):
insertIndex = bisect.bisect_left(rightHelper, nums[i])
#print('{},{}'.format(nums[i], insertIndex))
if insertIndex != 0:
maxRight[i] = rightHelper[insertIndex - 1]
rightHelper.insert(insertIndex, nums[i])
for i in range(len(nums)):
#print('{},{},{}'.format(nums[i], minLeft[i], maxRight[i]))
if minLeft[i] is not None and maxRight[i] is not None:
if maxRight[i] > minLeft[i]:
return True
```

We are actually looking for a 𝛬-shaped pattern in the array. For each element, we keep track of the minimal value to its left, and the maximal value that is smaller than the element to the right. If the value to the right is greater than the value to the left, we have found a 132 pattern.