Shortest Unsorted Continuous Subarray — LeetCode 581 Python Solution

The problem

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order. Return the shortest such subarray and output its length.

Example

Input

nums = [2,6,4,8,10,9,15]

Output

5

Explanation

You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Python solution

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        l, r = 0, len(nums) - 1
        while l <= r and nums[l] == arr[l]:
            l += 1
        while l <= r and nums[r] == arr[r]:
            r -= 1
        return r - l + 1

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 581. Shortest Unsorted Continuous Subarray is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems