Shortest Unsorted Continuous Subarray

To solve this problem, you need to find the shortest subarray such that if you only sort this subarray, the whole array will be sorted.

Here is the Python solution using a two pointer approach:

1. Initialize two pointers, left and right.
2. Start from the beginning of the array and keep moving right until you find an element that is greater than the next element. Similarly, start from the end of the array and keep moving left until you find an element that is less than the previous element. These two elements are your left and right pointers.
3. Find the minimum and maximum values in the subarray between left and right.
4. Extend the subarray to the left until all elements to the left are less than or equal to the minimum in the subarray. Similarly, extend the subarray to the right until all elements to the right are greater than or equal to the maximum in the subarray.
5. The length of the subarray between the updated left and right pointers (inclusive) is the shortest subarray that needs to be sorted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n - 1

        # find the first unsorted number from the start
        while left < n - 1 and nums[left] <= nums[left + 1]:
            left += 1

        # if the array is already sorted
        if left == n - 1:
            return 0

        # find the first unsorted number from the end
        while right > 0 and nums[right] >= nums[right - 1]:
            right -= 1

        subarray_min = min(nums[left: right + 1])
        subarray_max = max(nums[left: right + 1])

        # extend the subarray to the left
        while left > 0 and nums[left - 1] > subarray_min:
            left -= 1

        # extend the subarray to the right
        while right < n - 1 and nums[right + 1] < subarray_max:
            right += 1

        return right - left + 1

This code first finds the left and right boundaries of the unsorted subarray, and then expands these boundaries if necessary. It returns the length of the subarray that needs to be sorted.