Problem¶

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-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].

Constraints:

• n == nums.length
• 1 <= n <= 2 * 10**5
• -10**9 <= nums[i] <= 10**9

Solve¶

Normal - Keep go forward¶

We keep track of found range, and try to find n that in the middle

• To make the code faster, we can merge found range with each other
• A better data structure can be use like Binary Search Tree (?), but it quite hard to do so. Here I just done a minimal merge

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vector = []
        def combine(vector):
            min1, max1 = vector[0]
            min2, max2 = vector[-1]
            while min2 < min1 <= max1 <= max2:
                vector.pop(0)
                min1, max1 = vector[0]
            return vector

        min1 = max1 = None
        for n in nums:
            if min1 is not None and min1 < n < max1:
                return True
            if len(vector) > 0:
                vector = combine(vector)
                for min2, max2 in vector:
                    if min2 < n < max2:
                        return True
            if min1 is None:
                min1 = n
                max1 = n
                continue
            if n >= max1:
                max1 = n
                continue
            vector.append((min1, max1))
            min1 = max1 = n
        if min1 is not None:
            vector.append((min1, max1))
        # print(vector)

        return False

Sane - Backward¶

We going from backward, so the problem become find a minimum value in the 132 Pattern

• We want to keep track of possible min, current min and current max.
• If we found any number lower than current min then we found 132 pattern
• If we found a better current max, we update min in possible min to the best possible min value.

The possible min can be stored using a queue, which strictly increasing

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack, third = [], float('-inf')

        for num in reversed(nums):
            if num < third:
                return True
            while stack and stack[-1] < num:
                third = stack.pop()
            stack.append(num)
        return False