Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such
that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

Example 1:

Input: [1, 2, 3, 4]

Output: False

Explanation: There is no 132 pattern in the sequence.



Example 2:

Input: [3, 1, 4, 2]

Output: True

Explanation: There is a 132 pattern in the sequence: [1, 4, 2].



Example 3:

Input: [-1, 3, 2, 0]

Output: True

Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Difficulty: interview

Starter code:

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        

Solutions:
class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         
         if len(nums) < 3:
             return False
 
         stack = [[nums[0], nums[0]]]
         minimum = nums[0]
         for num in nums[1:]:
             if num <= minimum:
                 minimum = num
             else:
                 while stack and num > stack[-1][0]:
                     if num < stack[-1][1]:
                         return True
                     else:
                         stack.pop()
                 stack.append([minimum, num])
 
         return False
         """
         
         if len(nums) < 3:
             return False
         stack = [[nums[0], nums[0]]]
         m = nums[0]
         for num in nums[1:]:
             if num <= m:
                 m = num
             else:
                 while stack and num > stack[-1][0]:
                     if num < stack[-1][1]:
                         return True
                     else:
                         stack.pop()
                 stack.append([m, num])
         return False
     


class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         min_nums = [0] * len(nums)
         for i, num in enumerate(nums):
             min_nums[i] = min(min_nums[i-1], num) if i else num
 
         stack = []
         for i, num in reversed(list(enumerate(nums))):
             while stack and stack[-1] <= min_nums[i]:
                 stack.pop()
             if stack and num > stack[-1]:
                 return True
             else:
                 stack.append(num)
 
         return False

class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3:
             return False
         # initialize. 
         s2_candidate = [nums[-1]]
         cur_idx = len(nums)-2
         while cur_idx >= 0 and nums[cur_idx] <= s2_candidate[-1]:
             s2_candidate.append(nums[cur_idx])
             cur_idx-=1
         if cur_idx < 0:
             return False
         s3 = nums[cur_idx]
         while s2_candidate and s2_candidate[-1] < s3:
             s2 = s2_candidate.pop()
         
         # find s1
         cur_idx-=1
         while cur_idx >= 0:
             if nums[cur_idx] < s2:
                 return True
             elif nums[cur_idx] >= s3:
                 if nums[cur_idx] > s3:
                     s2 = s3
                 s3 = nums[cur_idx]
                 while s2_candidate and s2_candidate[-1] <= s3:
                     next_s2 = s2_candidate.pop()
                     if next_s2 > s2 and next_s2 < s3:
                         s2 = next_s2
             elif nums[cur_idx] < s3 and nums[cur_idx] > s2:
                 s2_candidate.append(nums[cur_idx])
             cur_idx-=1
 
         return False
                 
         


class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3: return False
         
         low = [float('inf')]
         high = [float('inf')]
         currlow, currhigh = nums[0], nums[0]
         for i in range(1, len(nums)):
             # print(nums[i])
             while nums[i] > high[-1]:
                 low.pop()
                 high.pop()
             if low[-1] < nums[i] < high[-1]:
                 return True
             if nums[i] == currlow or nums[i] == currhigh:
                 continue
             elif nums[i] < currlow:
                 low.append(currlow)
                 high.append(currhigh)
                 currlow, currhigh = nums[i], nums[i]
             elif nums[i] > currhigh:
                 currhigh = nums[i]
             else:
                 return True
             # print(currlow, currhigh)
             # print(low)
             # print(high)
         
         return False


class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         s3 = - 2 ** 64 - 1
         maxset = []
         for i in reversed(nums):
             if i < s3:
                 return True
             else:
                 while len(maxset) > 0 and i > maxset[-1]:
                     s3 = maxset.pop(-1)
             maxset.append(i)
         return False

class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         a= 1, b=3, c= 2
         """
         stack = []
         max_c = -math.inf
         for i in range(len(nums) - 1, -1, -1):
             if nums[i] < max_c:
                 return True
             while stack and stack[-1] < nums[i]:
                 max_c = max(max_c, stack.pop())
             stack.append(nums[i])
             
         return False

class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         stack = []
         for num in nums:
             if not stack or num < stack[-1][0]:
                 stack.append([num, num])
             elif num > stack[-1][0]:
                 if num < stack[-1][1]: return True
                 else:
                     node = stack.pop()
                     while stack and num >= stack[-1][1]:
                         stack.pop()
                     if stack and num > stack[-1][0]:
                         return True
                     stack.append([node[0], num])
         return False
             
                         
                         
             
                 
             
             
         


class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3:
             return False
         minx = nums[0]
         seg = [(nums[0], nums[0])]
         for x in nums[1:]:
             while seg and seg[-1][1] <= x:
                 seg.pop()
             if seg and x > seg[-1][0]:
                 return True
             minx = min(minx, x)
             seg.append((minx, x))
         return False

class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums:
             return False
         mins = [-1 for i in range(len(nums))]
         mins[0] = nums[0]
         
         for i in range(1, len(nums)):
             mins[i] = min(mins[i - 1], nums[i])
         s = []
         for i in range(len(nums) - 1, -1, -1):
             # print(i, s)
             if nums[i] != mins[i]:
                 while s and s[-1] <= mins[i]:
                     s.pop()
                 if s and s[-1] < nums[i]:
                     return True
                 s.append(nums[i])
         return False

class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if len(nums) < 3:
             return False
         
         minV = []
         for i in range(len(nums)):
             if i == 0:
                 minV.append(nums[i])
             else:
                 minV.append(min(nums[i], minV[-1]))
         
         st = []
         for j in range(len(nums)-1, 0, -1):
             if not st or nums[j] <= st[-1]:
                 st.append(nums[j])
             else:
                 while st and nums[j] > st[-1]:
                     s3 =  st.pop()
                 if s3 > minV[j]:
                     return True
                 st.append(nums[j])
                 
         return False
         
                 
             
                 
                  
 


class Solution:
     def find132pattern(self, nums):
         """
         :type nums: List[int]
         :rtype: bool
         """
         if not nums:
             return False
         mins = [-1 for i in range(len(nums))]
         mins[0] = nums[0]
         
         for i in range(1, len(nums)):
             mins[i] = min(mins[i - 1], nums[i])
         print(mins)
         s = []
         for i in range(len(nums) - 1, -1, -1):
             # print(i, s)
             if nums[i] != mins[i]:
                 while s and s[-1] <= mins[i]:
                     s.pop()
                 if s and s[-1] < nums[i]:
                     return True
                 s.append(nums[i])
         return False