Skip to main content

456. 132 Pattern

https://leetcode.com/problems/132-pattern/

Python​

Brute Force (Timelimit Exceed)​

  • Time: O(n^3)
  • Space: O(1)
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)

        if n < 3:
            return False

        for i in range(n-1):
            for j in range(i+1, n-1):
                if nums[i] > nums[j]:
                    continue
                for k in range(j+1, n):
                    if nums[i] < nums[k] and nums[k] < nums[j]:
                        return True

        return False

Brute Force - Remeber Min i (Timelimit Exceed)​

  • Time: O(n^2)
  • Space: O(1)
import math


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

        if n < 3:
            return False

        min_i = math.inf
        for j in range(n-1):
            min_i = min(min_i, nums[j])
            for k in range(j+1, n):
                if min_i < nums[k] < nums[j]:
                    return True

        return False

Prefix Sum (Min) with stack​

  • Time: O(n)
  • Space: O(n)
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)

        if n < 3:
            return False

        prefix_min = [nums[0]]
        for i in range(1, n):
            prefix_min.append(min(prefix_min[-1], nums[i]))

        stack = []
        for j in range(n-1, -1, -1):
            if nums[j] <= prefix_min[j]:
                continue

            while stack and stack[-1] <= prefix_min[j]:
                stack.pop()

            if stack and stack[-1] < nums[j]:
                return True

            stack.append(nums[j])

        return False