Leetcode question of the day

30- 132 Pattern

The problem can be found at the following link: Question Link

My Approach

We need to check if there exists three indices i,j and k such that i < j < k and nums[i] < nums[k] < nums[j]. To do this we'll have to first find if there exists a pair k, j for which k > j and at the same time nums[j] > nums[k]. Once this pair is found we need to find if we have a number to the left of j whose value is less than nums[k]. We can use monotonic stack for this.

1. Start with making our s3 = INT_MIN.

2. Initialise an empty stack st.

3. Now starting from our last index till the first index, i.e from i = n- 1 to i = 0, if our current number is lesser than s3 i.e nums[i] < s3, we've found our s1 we return true because we have already found a number s2 such that s3 < s2 so our sequence s1(nums[i]) < s3 < s2 is complete.

4. Else if nums[i] > s3 it means nums[i] could be our potential s2, so , while our nums[i] > the top of our stack, we pop and update the value of s3. The popping and updating is done because we need our s3 to be smaller than nums[i] since s3 < s2.

5. Push nums[i] into the stack.

6. At last return false, it would mean that our true isn't returned so no such sequence exists.

Time and Auxiliary Space Complexity

• Time Complexity: O(n)

• Auxiliary Space Complexity: O(n)

Code (C++)

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        int s3 = INT_MIN;
        stack<int> st;
        for(int i=n-1; i>=0; i--)
        {
            if(nums[i] < s3) return true;
            else
            {
                while(!st.empty() && nums[i] > st.top())
                {
                    s3 = st.top();
                    st.pop();
                }

                st.push(nums[i]);
            }
        }
        return false;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.