456. 132 Pattern (Python)

Related Topic

Stack.

Description

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.

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Sample I/O

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: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Note

n will be less than 15,000.

Methodology

To find 132 pattern. We should find left, mid and right three values. Mid value should be as larger as possible and right value should be smaller than mid but larger than other smaller values and left should be as smaller as possible than right. We will iterate the list in reversed order. We need a stack to store the temperory right values, once the current value is bigger than the top value (stack[-1]) value then we will know the right value = stack.pop() and there is 32 pattern. then we compare the new if new value is less than right value we will have 132 pattern.

def find132pattern(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        right = float('-inf')
        stack = []
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < right:
                return True
            else:
                while stack and stack[-1] < nums[i]:
                    right = stack.pop()
            stack.append(nums[i])
        return False

BigO

We iterate the list once so the total cost will be O(n)