find132Pattern.py

#  Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
#
# Note: n will be less than 15,000.
#
# Example 1:
#
# Input: [1, 2, 3, 4]
#
# Output: False
#
# Explanation: There is no 132 pattern in the sequence.
#
# Example 2:
#
# Input: [3, 1, 4, 2]
#
# Output: True
#
# Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
#
# Example 3:
#
# 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].


class Solution(object):
    def find132pattern(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        n = len(nums)
        if n < 3:
            return False
        my13 = []
        my1 = nums[0]
        my3 = 0
        for a in nums[1:]:

            if my1 < a < my3:
                return True
            for (b, c) in my13:
                if b < a < c:
                    return True
            if a < my1:
                my13.append((my1,my3))
                my1 = a
                my3 = a
            else:
                my3 =a

        return False