## 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 $% $ and $% $. 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.