Shortest Unsorted Continuous Subarray (Minimum Window Sort)

Two Pointer

Problem

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

For example:

Input: nums = [2,6,4,8,10,9,15]
Output: 5

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

Input: nums = [1,2,3,4]
Output: 0

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the 
subarray [5, 3, 7, 10, 9] to make the whole 
array sorted

Solution

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        i = 0
        j = len(nums) - 1
        
        while i < len(nums)-1 and nums[i] <= nums[i+1]:
            i+=1
        while j > 0 and nums[j-1] <= nums[j]:
            j-=1
            
        if i == len(nums)-1:
            return 0
        
        #need to find the min and max
        minN = float("inf")
        maxN = float("-inf")
        
        for k in range(i, j+1):
            minN = min(minN, nums[k])
            maxN = max(maxN, nums[k])
            
            
        while i > 0 and minN < nums[i-1]:
            i-=1
        while j < len(nums)-1 and maxN > nums[j+1]:
            j+=1
            
        return j - i + 1




#Utilizing two pointer approach by pointing to the 
#beginning and end of the array to find the elements
#that are not in order

#Identifying the maximum and minimum in this candidate
#subarray and "extending" the subarray to find the
#correct positions

#Time: O(n)
#Space: O(1)