132 Pattern — LeetCode 456 Python Solution

The 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

Input

nums = [1,2,3,4]

Output

false

Explanation

There is no 132 pattern in the sequence.

Python solution

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vk = -inf
        stk = []
        for x in nums[::-1]:
            if x < vk:
                return True
            while stk and stk[-1] < x:
                vk = stk.pop()
            stk.append(x)
        return False

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 456. 132 Pattern is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems