132 Pattern

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

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

Approach

Java

import java.util.Stack;

public class Pattern123 {
    public static void main(String[] args) {
        int[] nums = { 3, 1, 4, 2 };
        System.out.println(find132pattern(nums));
    }

    private static boolean find132pattern(int[] arr) {

        // find the length of array
        int n = arr.length;
        Stack<Integer> s = new Stack<Integer>();

        int min1 = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            // if we find the pattern then
            // return true
            if (min1 > arr[i]) {
                return true;

            }
            // update the min1 value
            while (!s.isEmpty() && s.peek() < arr[i]) {
                min1 = s.pop();
            }

            // add into the stack
            s.push(arr[i]);
        }
        return false;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

bool find132pattern(vector<int> &arr)
{

    //find the length of array
    int n = arr.size();
    stack<int> s;

    int min1 = INT_MIN;
    for (int i = n - 1; i >= 0; i--)
    {
        //if we find the pattern then
        //return true
        if (min1 > arr[i])
        {
            return true;
            
        }
        //update the min1 value
        while (!s.empty() && s.top() < arr[i])
        {
            min1 = s.top();

            //remove from the stack
            s.pop();
        }

        //add into the stack
        s.push(arr[i]);
    }
    return false;
}
int main()
{
    vector<int> nums = {3, 1, 4, 2};
    if (find132pattern(nums))
    {
        cout << "true";
    }
    else
    {
        cout << "false";
    }
    return 0;
}