Leetcode 132 Pattern problem solution

YASH PAL,

In this Leetcode 132 Pattern problem solution you are 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.

Leetcode 132 Pattern problem solution

Problem solution in Python.

class Solution:
    
    def find132pattern(self, nums) -> bool:
        stk = []
        top = -float("inf")
        
        for i in range(len(nums) -1, -1, -1):
            if top > nums[i]:
                return True
            
            while(len(stk) and nums[i] > stk[len(stk) -1]):
                top = stk.pop()
            stk.append(nums[i])
        return False

Problem solution in Java.

class Solution {
public boolean find132pattern(int[] nums) {

    if(nums==null||nums.length<3) return false;
    int[] min=new int[nums.length];
    int[] max=new int[nums.length];
    min[0]=nums[0];
    max[0]=nums[0];
    for(int i=1;i<nums.length;i++){
        if(nums[i]>=max[i-1]){
            max[i]=nums[i];
            min[i]=min[i-1];
        }
        else if(nums[i]<=min[i-1]){
            min[i]=nums[i];
            max[i]=max[i-1];
        }
        else{
            int j=0;
            for( j=i-1;j>=1;j--){
                if(nums[j]>nums[i])
                    break;
            }
            if(j>=1&&min[j-1]<nums[i])
                return true;
            max[i]=max[i-1];
            min[i]=min[i-1];
        }
    }
    return false;
}
}

Problem solution in C++.

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        vector<int> min_array(n);
        min_array[0] = nums[0];
        for(int i = 1; i < n; i++) {
            min_array[i] = min(min_array[i-1], nums[i]);
        }
        vector<int> st;
        for(int i = n-1; i >= 0; i--) {
            if(!st.empty() && nums[i] > min_array[i] && nums[i] < st.back() &&
               min_array[i] < st.back()) st.push_back(nums[i]);
            else  if(st.empty()) st.push_back(nums[i]);
            else if(nums[i] == min_array[i]) continue;
            else {
                while(!st.empty() && nums[i] > st.back() && st.back() <= min_array[i]) st.pop_back();
                if(!st.empty() && nums[i] > st.back() && st.back() > min_array[i]) return true;
                else st.push_back(nums[i]);
            }
            
        }
        return false;
    }
};

Problem solution in C.

bool find132pattern(int *nums, int size)
{
    int index = size, n3 = INT_MIN;

    for (int i = size - 1; i > -1; i--) {
        if (nums[i] < n3)
            return true;

        while (index < size && nums[i] > nums[index]) {
            n3 = nums[index];
            index++;
        }

        index--;
        nums[index] = nums[i];
    }

    return false;
}

coding problems solutions