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].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

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

Solutions:
class Solution:

	def find132pattern(self, nums):
		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):
		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):
		if len(nums) < 3:
			return False
		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()
		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):
		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)):
			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
		return False


class Solution:

	def find132pattern(self, nums):
		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):
		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):
		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):
		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):
		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):
			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):
		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