LeetCode 581. Shortest Unsorted Continuous Subarray

September 11, 2020

We could sort the list

with a comparison sort in $O(n*log(n))$ time. And then, in $O(n)$ time, we can compare the ends of the sorted and input versions to see where the input list starts getting out of sorted order.

Can we do better than $O(n*log(n))$ ?

How about a bucket sort? The problem says $1 \geq n \leq 10,000$ and doesn't limit the range of input values, so a bucket sort would be much worse in the worst case than a comparison sort.

We could avoid a full sort by using a stack

Starting at the start of the list with an empty stack, we step forward, adding elements to the stack as long as they're increasing. If that continues for the whole list, the list is already sorted. Whenever we find a value that smaller than elements in the stack, we pop elements from the stack until that's no longer true. After getting through the whole list, we'll have a stack containing all elements from the start of the list that are both sorted and smaller than all other elements in the list. We can do that in reverse from the end of the list and then figure out how large the unsorted subarray is.

This solution is $O(n)$ .

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]), 5)

    def test_empty(self):
        self.assertEqual(self.s.findUnsortedSubarray([]), 0)

    def test_start(self):
        self.assertEqual(self.s.findUnsortedSubarray([1,2,3,4,9,5,6,7,8]), 5)

    def test_end(self):
        self.assertEqual(self.s.findUnsortedSubarray([2,3,4,1,5,6,7,8,9]), 4)

    def test_middle(self):
        self.assertEqual(self.s.findUnsortedSubarray([1,2,3,4,7,5,6,8,9]), 3)

class Solution:

    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        s = [nums[0]]
        failed = False
        for i in range(1, len(nums)):
            if not failed and nums[i] >= s[-1]:
                s.append(nums[i])
                continue
            failed = True
            while s and nums[i] < s[-1]:
                s.pop()
            if not s:
                break
        c = len(s)
        if c == len(nums):
            return 0
        s = [nums[-1]]
        failed = False
        for i in range(len(nums)-2, -1, -1):
            if not failed and nums[i] <= s[-1]:
                s.append(nums[i])
                continue
            failed = True
            while s and nums[i] > s[-1]:
                s.pop()
            if not s:
                break
        return len(nums) - len(s) - c


if __name__ == "__main__":
    unittest.main()