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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

132 Pattern

Number: 456

Difficulty: Medium

Paid? No

Companies: Google, Amazon, TikTok, Apple, Adobe, Microsoft, IBM, Goldman Sachs

Problem Description

Given an array of integers, determine if there exists a subsequence of three numbers (nums[i], nums[j], nums[k]) such that i < j < k and nums[i] < nums[k] < nums[j]. This pattern is called the "132 pattern" because the values of the subsequence resemble the order: first (1), then (3), then (2).

Key Insights

  • The challenge is to efficiently detect a subsequence that satisfies nums[i] < nums[k] < nums[j].
  • A brute force approach checking all triples would be too slow given the constraints.
  • Using a monotonic stack in reverse order allows us to keep track of potential candidates for nums[k] and check for a valid pattern.
  • We maintain a variable to store the possible "2" element (candidate for nums[k]) as we move from right to left.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) in the worst case for the stack.

Solution

We solve the problem by iterating through the list in reverse order while using a stack to maintain potential candidates for the "middle" element (nums[j]). We also use a variable (let’s call it candidate) to represent the best candidate for nums[k] that we have seen so far. For each element in the reversed array:

  1. If the current element is less than the candidate, we have found a valid 132 pattern.
  2. Otherwise, while the stack is not empty and the current element is greater than the top of the stack, we update the candidate by popping from the stack.
  3. Push the current element onto the stack as a potential future candidate. This approach efficiently identifies whether a 132 pattern exists.

Code Solutions

# Python solution for the 132 Pattern problem

def find132pattern(nums):
    # Initialize candidate for nums[k] with a very small value
    candidate = float('-inf')
    stack = []  # Stack to keep potential nums[j] elements

    # Traverse the array in reverse order
    for num in reversed(nums):
        # If current number is less than candidate, we found a valid 132 pattern
        if num < candidate:
            return True
        # Update the candidate while current number is greater than the element at stack's top
        while stack and num > stack[-1]:
            candidate = stack.pop()
        # Push the current number onto the stack for potential future use
        stack.append(num)
    return False

# Example usage:
# print(find132pattern([3, 1, 4, 2]))  # Output: True
← Back to All Questions