algoadvance

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.

Example 1:

Input: nums = [1, 2, 3, 4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3, 1, 4, 2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1, 3, 2, 0]
Output: true
Explanation: There are several 132 patterns in the sequence: [-1, 3, 2] and [-1, 3, 0].

Clarifying Questions

  1. Are the elements of the array unique?
    • No, the elements can have duplicates.
  2. What is the range of the elements in the array?
    • The elements can be any integer within typical integer limits.
  3. Is there any specific time complexity requirement?
    • Ideally, an efficient solution would be preferable, preferably better than O(n^2).

Strategy

To solve this problem efficiently, an O(n) time complexity solution can be used via a stack-based approach. Here’s the strategy:

  1. Maintain a stack and a variable sec (second highest):
    • Traverse the array from the end to the beginning.
    • Use the stack to track potential nums[k] (values which might be the middle one in the 132 pattern).
    • sec will help us ensure we have a valid candidate for nums[i].
  2. Iterate from the end of the array:
    • For each element, the key idea is to determine if it can be nums[i].
    • Compare the current element to sec to see if nums[i] < nums[k] where nums[k] is a previously seen value.
    • Pop elements from the stack if they are less than the current value (possible nums[k] for a future nums[j]).
    • Push the current element onto the stack to be a potential future nums[j].

Code

Here’s the implementation in Python:

def find132pattern(nums):
    if len(nums) < 3:
        return False
    
    stack = []
    sec = float('-inf')  # This will hold the second highest number in the 132 pattern
    
    # Traverse backwards
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] < sec:
            return True
        while stack and nums[i] > stack[-1]:
            sec = stack.pop()
        stack.append(nums[i])
    
    return False

# Test cases
print(find132pattern([1, 2, 3, 4]))  # Output: False
print(find132pattern([3, 1, 4, 2]))  # Output: True
print(find132pattern([-1, 3, 2, 0])) # Output: True

Time Complexity

This solution efficiently finds the 132 pattern using stack operations, ensuring optimal performance for larger inputs.

Try our interview co-pilot at AlgoAdvance.com