Stack One Pass O(N) space O(N)

main idea: i1,i2,i3 ==> n1 < n3 < n2, how can we get n3 before we get n2? reverse loop + stack Hence, i3> i2 > i1, we need to ensure n2 > n3 > n1 ==> each time compare current num with top of stack n2 ? n3 , if n2 > n3, means we find n3 is on top of stack, pop off and save s3, how do we find n1? compare n1 ? n3 since loop will continue, later number is position wise smaller than previous number after we find n3. only if n3 > current n , we find 1, exit loop

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

LTE brute force

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        _min = float('inf')
        size = len(nums)
        for j in range(size-1):
            _min = min(_min,nums[j])
            for k in range(j+1,size):
                if nums[k]<nums[j] and nums[k] > _min:
                    return True
        return False

TODO: other solutions