<p>Given an integer array <code>nums</code>, you need to find one <b>continuous subarray</b> such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.</p>

<p>Return <em>the shortest such subarray and output its length</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,6,4,8,10,9,15]
<strong>Output:</strong> 5
<strong>Explanation:</strong> You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Can you solve it in <code>O(n)</code> time complexity?
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        
        l,r = len(nums)-1, 0
        # to find left boudary
        stck=[] # increasing stack
        for i in range(len(nums)):
            while stck and nums[stck[-1]]>nums[i]:
                l = min(l, stck.pop())
            stck.append(i)

        # to find right boudary        
        stck=[]  # decreasing stack (backward)      
        for i in range(len(nums)-1,-1, -1):
            while stck and nums[stck[-1]]<nums[i]:
                r = max(r, stck.pop())
            stck.append(i)
        
        return 0 if l >= r else r-l+1        


'''
Algorithm

The idea behind this approach is also based on selective sorting. We need to determine the correct position of the minimum and the maximum element in the unsorted subarray to determine the boundaries of the required unsorted subarray.

To do so, in this implementation, we make use of a stack. We traverse over the nums array starting from the beginning. As we go on facing elements in ascending order(a rising slope), we keep on pushing the elements' indices over the stack. This is done because such elements are in the correct sorted order(as it seems till now). As soon as we encounter a falling slope, i.e. an element nums[j] which is smaller than the element on the top of the stack, we know that nums[j] isn't at its correct position.

In order to determine the correct position of nums[j], we keep on popping the elements from the top of the stack until we reach the stage where the element(corresponding to the index) on the top of the stack is lesser than nums[j]. Let's say the popping stops when the index on stack's top is k. Now, nums[j] has found its correct position. It needs to lie at an index k+1.

We follow the same process while traversing over the whole array, and determine the value of minimum such k. This marks the left boundary of the unsorted subarray.

Similarly, to find the right boundary of the unsorted subarray, we traverse over the nums array backwards. This time we keep on pushing the elements if we see a falling slope. As soon as we find a rising slope, we trace forwards now and determine the larger element's correct position. We do so for the complete array and thus, determine the right boundary.

We can look at the figure below for reference. We can observe that the slopes directly indicate the relative ordering. We can also observe that the point b needs to lie just after index 0 marking the left boundary and the point a needs to lie just before index 7 marking the right boundary of the unsorted subarray.
'''
17400