Description:

Given a sequence of integers , a 132 pattern is a subsequence , , 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:

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.