Untitled

"""

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.

test_cases = [
    ([1,2,3,4], False),
    ([3,1,4,2], True),
    ([-1,3,2,0], True),
]

2,4,1 False

1, 4, 2 True

1, 4, 1 False
"""

import math

def solution(nums):
    if len(nums) < 3:
        return False
    
    smallestTilNow = [math.inf for _ in nums]
    
    for i, num in enumerate(nums):
        if i - 1 >= 0:
            num = min(num, smallestTilNow[i-1])
        smallestTilNow[i] = num
        
#     for i, num in enumerate(nums):
#         if smallestTilNow[i] >= num:
#             continue
            
#         for rightNum in nums[i+1:]:
#             if smallestTilNow[i] < rightNum < num:
#                 return True

    stack = []
    
    for i in range(len(nums)):
        i = len(nums) - 1 - i
        center_num = nums[i]
        
        if stack and stack[-1] >= center_num:
            stack.pop()
        
        if stack and stack[-1] > smallestTilNow[i]:
            return True
            
        stack.append(center_num)
            
    return False

test_cases = [
    ([1,2,3,4], False),
    ([3,1,4,2], True),
    ([-1,3,2,0], True),
]

for test_case, ans in test_cases:
    print(solution(test_case) == ans)