We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

132 Pattern

Difficulty: Medium

Problem Description

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j], and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. Return true if there is a 132 pattern in nums, otherwise return false.

Key Insights

  • The problem requires identifying a specific subsequence in an array of integers.
  • A brute force approach would involve checking all triplets, which is inefficient.
  • Using a stack can help efficiently track potential candidates for the "2" in the "132" pattern.
  • We can traverse the array backward to maintain the order of indices and simplify the comparison.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can utilize a stack to keep track of potential "3" values while iterating through the array in reverse. We will maintain a variable to hold the "2" value, and for each element, we check if we can find a valid "1" that is less than the current element. The stack allows us to efficiently find the maximum "3" value that meets the conditions.

Code Solutions

def find132pattern(nums):
    if len(nums) < 3:
        return False

    stack = []
    third = float('-inf')

    for num in reversed(nums):
        if num < third:
            return True
        while stack and num > stack[-1]:
            third = stack.pop()
        stack.append(num)

    return False
← Back to All Questions