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

The goal of this problem is to find two numbers beg and end, such that difference of them is as small as possible and also such that if we sort nums from beg to end we will have fully sorted data.

Let run_max be running maximum of nums.

What is the end pointer? It is the smallest value such that

max(nums[0], nums[1], ..., nums[end]) <= nums[end + 1] <= nums[end + 2] <= ... <= nums[-1]:

first inequality holds, because after we sort data inside, we still need to be less than nums[end + 1], and the rest inequalites are definition that data after end is already sorted.

Now, let us start from the end of our data and move to the left, checking if condtion holds. While it holds, we decrease end by one. Then we check if we reached 0 and if we did, we can immedietly return 0, because data is sorted. If not, we do similar logic, starting with beginning of our data and moving to the right.

Complexity: time complexity is O(n), we iterate just several times through our data. Space complexity is also O(n), which can also be reduced to O(1), but in my opinion the solution becomes much less intuitive.

class Solution:
    def findUnsortedSubarray(self, nums):
        nums = [-float("inf")] + nums + [float("inf")]
        run_max = list(accumulate(nums, max))
        run_min = list(accumulate(nums[::-1], min))[::-1]
        
        end, beg = len(nums) - 1, 0

        while nums[end-1] <= nums[end] and run_max[end-1] <= nums[end - 1]:
            end -= 1
            
        if end == 0: return 0
            
        while nums[beg+1] >= nums[beg] and run_min[beg+1] >= nums[beg + 1]:
            beg += 1
            
        return end - beg - 1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0581