456. 132 Pattern

'''
why we have to keep small variable why not just use min_so_far in
stack tuple?
Because min_so_far will just denote minimum till the tuple element
is present.
where as small will denote whole smallest till present ruunning index
'''
class Solution:
    def find132pattern(self, a: List[int]) -> bool:
        small=float('inf')
        st=[] #store(val,min_so_far_before curr val)
        for i in a:
            while st and st[-1][0]<=i:
                st.pop()
            if st and st[-1][1]<i:
                return True
            st.append((i,small))
            small=min(small,i)
        return False
'''
we will keep a variable smallest to know the smallest number to the left (index i) of the current element (index j) so that there will be higher chance we find k which k > j > i and A[j] > A[k] > A[i] (because now we already have j > i and A[j] > A[i] the only thing we need to do is find if there is a element to the right of A[j] which smaller than A[j] and greater than A[i]), each time we will pop the stack until the last number of the last element in the stack greater than the current number, if Stack[-1][0] > current element it means we found 1 3 2 pattern (this step is exactly the same with finding previous greater element).
'''