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.
Start with making our
s3 = INT_MIN
.Initialise an empty stack st.
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.enums[i] < s3
, we've found our s1 we return true because we have already found a number s2 such thats3 < s2
so our sequences1(nums[i]) < s3 < s2
is complete.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] sinces3 < s2
.Push
nums[i]
into the stack.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++)
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.
Last updated