Stack Sortable Array

Hi, so there is this question in leetcode…

QUESTION LINK

This question is asking us to find “132” pattern in the array. This reminds me of the stack-sortable permutation, which was introduced by Knuth. Please read the detailed explanation at the Wikipedia first.

Stack-sortable permutations are the sequence of numbers that are sortable using a stack and thus it should not contain “231” pattern. Once you read the article, you can easily understand why the “231” pattern prevents it from being sorted.

This question is very similar with the problem that identifies the sequence of number is stack-sortable or not.

So if we reverse the array and find if its sortable or not [ this will help us to find whether the reversed array has a “231” pattern or not , and in turn “132” pattern in the original array ]

So i coded this out, but unfortunately i am facing WA in some test cases.

MY CODE:

// I am checking if the array is sorted or not, based on the wiki page code..
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> s;
        reverse(nums.begin(),nums.end());
        vector<int> a;
        for(auto x:nums){
            while(!s.empty() and x>=s.top())
            {a.push_back(s.top());
                s.pop();
            }
            s.push(x);
        }
        while(!s.empty()){
            a.push_back(s.top());
            s.pop();
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=a[i]) return 1;
        }
        return 0;
    }
};

Help is appreciated thanks
@galencolin @akshitm16 @triveni @carre

EDIT: So it turns out i missed some cases where the array looks like [1,3,3] which is stack sortable but not of the pattern 132, how can i edit my existing sol to cover this up

Shouldn’t this if(!s.empty() and x >= s.top()) be a while loop?
It still doesn’t pass though…

[UPD]: That’s because even 331 is not stack sortable. So we’ll be returning true for the input array [1, 3, 3] when the expected answer is false.

1 Like

Ohh, yes you are right.

Any idea how to tackle this?

I tried a different approach altogether.

Code
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        vector<int> prevGreater(n, -1), firstLesser(n, -1);
        stack<int> s;
        for(int i = n - 1; i >= 0; i--)
        {
            while(!s.empty() && nums[s.top()] < nums[i])
            {
                prevGreater[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    firstLesser[i] = j;
                    break;
                }
            }
        }
        
        for(int i = 0; i < n; i++)
        {
            if(prevGreater[i] != -1 && firstLesser[i] != -1 && firstLesser[i] < prevGreater[i])
                return true;
        }
        
        return false;
    }
};

The runtime is O(n^2) though :stuck_out_tongue: . It passes, but I’m trying to optimise it!

1 Like

There is a simple way to solve this in O(n\log{n}) with the data structure “set”.
Iterate j from 1 to n. Maintain the set of all elements to the right and left to a_j. Check if the smallest element less than a_j in the left set is lesser than the largest element less than a_j in the right set. If it is, then there is a 1 \ 3\ 2, else check the next j.

1 Like

“spam”?

I meant brute force.

1 Like

Just to follow your intended approach you could make some small changes:

  • Make sure that equal values ​​are kept together removing the equal condition to pop the stack, that is, change >= for >

  • verify sorted or reversed-sorted of you stack-sorted vector a.

Code
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> s;
        reverse(nums.begin(),nums.end());
        vector<int> a;
        for(auto x:nums){
            while(!s.empty() and x>s.top())
            {a.push_back(s.top());
                s.pop();
            }
            s.push(x);
        }
        while(!s.empty()){
            a.push_back(s.top());
            s.pop();
        }
        sort(nums.begin(),nums.end());
        bool ok=true;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=a[i]) {ok=false;break;}
        }
        if (ok) return 0;
        reverse(a.begin(),a.end());
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=a[i]) return 1;
        }
        return 0;
    }
};
1 Like

cool ty

Hey , this code passed too


        class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> s;
        reverse(nums.begin(),nums.end());
        vector<int> a;
        for(auto x:nums){
            while(!s.empty() and x>s.top())
            {a.push_back(s.top());
                s.pop();
            }
            s.push(x);
        }
        while(!s.empty()){
            a.push_back(s.top());
            s.pop();
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=a[i]) return 1;
        }
        return 0;
    }
};

Changing the >= to > did the job, can you elaborate why this works?

EDIT: - to take care of duplicates in the array right?

yes, you’re right, that’s enough; and yes, the >= symbol was not working well in cases like

2 2 1 (already reversed)

With >= the vector generated is 2 1 2; while is 1 2 2 if you use > instead.