Description
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 1:
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.
Example 2:
Input: nums = [1,2,3,4] Output: 0
Example 3:
Input: nums = [1] Output: 0
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 105
Follow up: Can you solve it in
O(n) time complexity?
Solution
Python3
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
N = len(nums)
prev = nums[0]
end = 0
for i in range(1, N):
if nums[i] < prev:
end = i
else:
prev = nums[i]
prev = nums[-1]
start = N - 1
for i in range(N - 2, -1, -1):
if nums[i] > prev:
start = i
else:
prev = nums[i]
if end != 0:
return end - start + 1
return 0