LeetCode 456. 132 Pattern
06 Sep 2018Description:
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:
Falseexplanation:
There is no 132 pattern in the sequence.
input:
[3,1,4,2]output:
Trueexplanation:
There is a 132 pattern in the sequence:
[1, 4, 2].
input:
[-1,3,2,0]output:
Trueexplanation:
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.