# Untitled

unknown
python
2 years ago
1.5 kB
11
Indexable
Never
```"""

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)
```