Leetcode question of the day
Last updated
Was this helpful?
Last updated
Was this helpful?
The problem can be found at the following link:
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.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.
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
.
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 Complexity: O(n)
Auxiliary Space Complexity: O(n)
For discussions, questions, or doubts related to this solution, please visit our . 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 repository.