# Python solution in O(nlogn)

• I tried multiple O(n^2) solutions and it seems only O(nlogn) is accepted for Python.

First we make the `left` list that maintains the min value up to index `i`.
Then we make the `right` list backward that maintains the smallest number that is larger than `left[i]` up to `i` using a heap.
Finally we iterate through `nums` and check if `left[i] < right[i] < num`.

``````import heapq

class Solution(object):
def find132pattern(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums:
return False
left = [nums[0]]
for num in nums[1:]:
left.append(min(left[-1], num))
q = []
right = [None] * len(nums)
for i, num in enumerate(nums[::-1]):
heapq.heappush(q, num)
while q and q[0] <= left[len(nums) - i - 1]:
heapq.heappop(q)
if q:
right[len(nums) - i - 1] = q[0]
for i, num in enumerate(nums):
if right and left[i] < right[i] < num:
return True
return False
``````

• @Uduse Shouldn't it be:

``````...
if right[i] and left[i] < right[i] < num:
...``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.