E-581. Shortest Unsorted Continuous Subarray

Loading...LeetCode

# 2: O(n), O(1)
'''
    观察一下subarray和整体array的关系.
    在未排序的subarray的部分, 我们知道这个subarray里面的最大值要比排序部分的右半部分最小值要
    小, 同理未排序部分最小值要比排序部分左半部分最大值要大.
    
    所以未排序subarray的右边界, 即end的值肯定是小于(注意是严格小于)subarray里最大值, 也小于排
    序右半部分的最小值.
    同理未排序subarray的左边界, 即start的值肯定是大于(同上严格大于)subarray里最小值, 也大于
    排序左半部分的最大值.
            
    所以我们从左往右, 保留当前遇到的最大值max, 并且与cur遍历到的值nums[cur]进行比较, 如果这
    两个值相等, 说明当前nums[cur]最大, 顺序上没有问题, 如果nums[cur]要小于当前max, 说明这个
    nums[cur]可以作为一个潜在的右边界, 一直遍历到最右边, 结束.
    反之亦然.
    
    所以我们稍微抽象一下:
    从左往右, 找到最右的那个比(当前已经遍历过的所有数后找到的最大值)要小的值的indice end.
    从右往左, 找到最左的那个比(当前已经遍历过的所有数后找到的最小值)要大的值的indice start.
    
    result = end - start + 1 
'''
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if nums == None: 
            return 0
        
        if len(nums) == 0 or len(nums) == 1:
            return 0

        maximum = float('-inf')
        end = -2
        for i in range(0, len(nums)):
            maximum = max(maximum, nums[i])
            if nums[i] < maximum:
                end = i

        minimum = float('inf')
        begin = -1
        for i in range(len(nums)-1, -1 ,-1):
            minimum = min(minimum, nums[i])
            if nums[i] > minimum:
                begin = i

        return end - begin + 1
        
# 0 O(nlogn), O(n)
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums)
        start = 0
        end = len(nums) - 1
        while start < len(nums) and nums[start] == sorted_nums[start]:
            start += 1
        while end >= start and nums[end] == sorted_nums[end]:
            end -= 1
        return end - start + 1

# 1 O(n), O(1)
# https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103067/Python-O(N)-with-O(1)-space-complexity.-No-sorting
# https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103057/java-on-time-o1-space
# https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/264474/Python-O(n)-2-Loops-and-O(1)-space
'''
    Such as following example that would not get caught by first pass:
    
    [1, 3, 7, 2, 5, 4, 6, 10] : left would catch at value 7, index: 2 and right 
    would catch at value 4, index: 5
    
    But, looking at the array the function should also include 3 and 6. And this 
    is why we do another round of while loop.
    
    Instead incrementing and decrementing respective, l and r, we decrement and 
    increment respective l and r.
    
    Thinking about it as adjusting lower bound and upper bound is better.
    This adjustment depends on two things: Minimum and maximum values of array 
    nums[l:r+1].
    
    Now, we decrement l value until we find something that is lower than minimum.
    
    Also, we increment r value until we find something that is greater than maximum.
    
    After all that you just need to do l + r - 1.
'''
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        def find_min_max(l,r):
            local_minimum = float('inf')
            local_maximum = float('-inf')
            for i in range(l, r + 1):
                if i == len(nums):
                    break
                local_minimum = min(local_minimum, nums[i])
                local_maximum = max(local_maximum, nums[i])
                
            return local_minimum, local_maximum
        
        if len(nums) < 2:
            return 0
        
        l, r = 0, len(nums) -1
        
        while l < len(nums) - 1 and nums[l] <= nums[l + 1]:
            l += 1
        
        while r > 0 and nums[r] >= nums[r -1]:
            r -= 1
            
        if l > r:
            return 0
            
        tempMin, tempMax = find_min_max(l, r+1)
        
        while l > 0 and tempMin < nums[l-1]:
            l -= 1
        
        while r < len(nums) - 1 and tempMax > nums[r+1]:
            r += 1
            
        return r - l + 1