Leetcode 581 Solution

This article provides solution to leetcode question 581 (shortest-unsorted-continuous-subarray)
Categories:
Tags:
Access this page by simply typing in "lcs 581" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/shortest-unsorted-continuous-subarray

Solution

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        l = len(nums) - 1
        i = 0
        s = []
        while i < len(nums):
            num = nums[i]

            popped = False
            while s and s[-1][0] > num:
                s.pop(-1)
                popped = True

            if popped:
                l = min(l, s[-1][1] + 1) if s else 0

            s.append((num, i))
            i += 1

        r = 0
        i = len(nums) - 1
        s = []
        while i >= 0:
            num = nums[i]

            popped = False
            while s and s[-1][0] < num:
                s.pop(-1)
                popped = True

            if popped:
                r = max(r, s[-1][1] - 1) if s else len(nums) - 1
                print(r)

            s.append((num, i))
            i -= 1

        print(l, r)
        return r - l + 1 if r > l else 0