Python solution in O(nlogn)


  • 2

    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
    

  • 0
    P

    @Uduse Shouldn't it be:

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

Log in to reply
 

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