456. 132 Pattern

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.

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 three 132 patterns in the sequence: [-1,3,2], [-1,3,0] and [-1,2,0].

Constraints:

• n == nums.length
• 1 <= n <= 2 * 10⁵
• -10⁹ <= nums[i] <= 10⁹

Python Solution

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        # Stack to store potential "2" values
        stack = []
        # Keep track of potential "2" value
        s3 = float('-inf')
        
        # Iterate from right to left
        for num in reversed(nums):
            # If we find a value smaller than s3, we have found a 132 pattern
            if num < s3:
                return True
            
            # Update s3 with values that could be "2"
            while stack and stack[-1] < num:
                s3 = stack.pop()
            
            # Add current number as potential "3"
            stack.append(num)
        
        return False

Java Solution

class Solution {
    public boolean find132pattern(int[] nums) {
        // Stack to store potential "2" values
        Stack stack = new Stack<>();
        // Keep track of potential "2" value
        int s3 = Integer.MIN_VALUE;
        
        // Iterate from right to left
        for (int i = nums.length - 1; i >= 0; i--) {
            // If we find a value smaller than s3, we have found a 132 pattern
            if (nums[i] < s3) {
                return true;
            }
            
            // Update s3 with values that could be "2"
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                s3 = stack.pop();
            }
            
            // Add current number as potential "3"
            stack.push(nums[i]);
        }
        
        return false;
    }
}

C++ Solution

class Solution {
public:
    bool find132pattern(vector& nums) {
        // Stack to store potential "2" values
        stack stack;
        // Keep track of potential "2" value
        int s3 = INT_MIN;
        
        // Iterate from right to left
        for (int i = nums.size() - 1; i >= 0; i--) {
            // If we find a value smaller than s3, we have found a 132 pattern
            if (nums[i] < s3) {
                return true;
            }
            
            // Update s3 with values that could be "2"
            while (!stack.empty() && stack.top() < nums[i]) {
                s3 = stack.top();
                stack.pop();
            }
            
            // Add current number as potential "3"
            stack.push(nums[i]);
        }
        
        return false;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    // Stack to store potential "2" values
    const stack = [];
    // Keep track of potential "2" value
    let s3 = -Infinity;
    
    // Iterate from right to left
    for (let i = nums.length - 1; i >= 0; i--) {
        // If we find a value smaller than s3, we have found a 132 pattern
        if (nums[i] < s3) {
            return true;
        }
        
        // Update s3 with values that could be "2"
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            s3 = stack.pop();
        }
        
        // Add current number as potential "3"
        stack.push(nums[i]);
    }
    
    return false;
};

C# Solution

public class Solution {
    public bool Find132pattern(int[] nums) {
        // Stack to store potential "2" values
        Stack stack = new Stack();
        // Keep track of potential "2" value
        int s3 = int.MinValue;
        
        // Iterate from right to left
        for (int i = nums.Length - 1; i >= 0; i--) {
            // If we find a value smaller than s3, we have found a 132 pattern
            if (nums[i] < s3) {
                return true;
            }
            
            // Update s3 with values that could be "2"
            while (stack.Count > 0 && stack.Peek() < nums[i]) {
                s3 = stack.Pop();
            }
            
            // Add current number as potential "3"
            stack.Push(nums[i]);
        }
        
        return false;
    }
}