1
# Runtime: 250 ms (Top 81.05%) | Memory: 16.2 MB (Top 5.39%)
2
# lets start adding elements to stack. We have to fin the min length [a, b] interval (corresponding to the problem description).
3
# a has to be the first element's index we pop from the array. lets say y is the last element's index we pop.
4
# and max_pop is the maximum element(not index) we pop during stacking.After stacking process is done we are going to have
5
# last elements in the stack E(E is the stack after stacking is done).We have to find M = maximum_element(max_pop, all elements of E)
6
# Index of M is going to be right edge of the [a, b] interval
7

8

9
class Solution:
10
    def findUnsortedSubarray(self, nums) -> int:
11
        stack = []
12
        min_index = len(nums)
13
        max_index = 0
14
        max_pop = float("-inf")
15
        for i in range(len(nums)):
16
            while stack and nums[i] < stack[-1][0]:
17

18
                p = stack.pop()
19
                if p[0] > max_pop:
20
                    max_pop = p[0]
21
                if p[1] < min_index:
22
                    min_index = p[1]
23
                if p[1] > max_index:
24
                    max_index = p[1]
25
            stack.append([nums[i], i])
26
        max_r = max_index
27
        for st in stack:
28
            if st[0] < max_pop:
29
                max_r = st[1]
30
        if min_index == len(nums):
31
            return 0
32
        return max_r - min_index + 1