132 Pattern - Leetcode Solution

The 132 Pattern problem on LeetCode is a problem that asks you to find if there is a subsequence of numbers in an input array that satisfies the pattern "132". The pattern "132" is defined as follows:

A subsequence of the input array consists of three elements, such that:

1. The first element is smaller than the third element
2. The second element is greater than the first element, and less than the third element.

For example, in the sequence [3, 1, 4, 2], there is a subsequence [3, 4, 2], which satisfies the pattern "132".

We can solve this problem using a stack data structure. The idea behind the solution is to push the maximum value seen so far onto a stack, and then look for a value that is less than the maximum value on the stack, while also being greater than any previously seen values. If we find such a value, then we have a 132 pattern.

Here is a step by step algorithm to solve the 132 Pattern problem:

1. Create an empty stack.
2. Initialize the minimum value seen so far to the first element of the input array.
3. Loop through the input array starting from the second element.
4. While the stack is not empty and the current element is less than the top element of the stack, pop elements off the stack and update the minimum value seen so far.
5. If the current element is greater than the minimum value seen so far, push it onto the stack.
6. If the current element is greater than the top element of the stack, then we have found a 132 pattern. Return true.
7. If we haven't found a 132 pattern, return false.

Here is the Python code that implements this algorithm:

def find132pattern(nums):
    stack = []
    minVal = float('-inf')
    
    for num in reversed(nums):
        if num < minVal:
            return True
        while stack and stack[-1] < num:
            minVal = stack.pop()
        stack.append(num)
        
    return False

The time complexity of this solution is O(n), where n is the length of the input array. This is because each element of the input array is pushed onto the stack and popped off at most once. The space complexity is also O(n), because the stack can potentially hold all n elements of the input array.

1