diff options
Diffstat (limited to 'shortest_subarr_remove_sort.py')
-rw-r--r-- | shortest_subarr_remove_sort.py | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/shortest_subarr_remove_sort.py b/shortest_subarr_remove_sort.py new file mode 100644 index 0000000..5587aa7 --- /dev/null +++ b/shortest_subarr_remove_sort.py @@ -0,0 +1,39 @@ +# 1574. Shortest Subarray to be Removed to Make Array Sorted + +""" +given an integer array 'arr', remove a subarray (can be empty) from 'arr' +such that the remaining elements in 'arr' are non-decreasing. return the +length of the shortest subarray to remove. a subarray is a contiguous +subsequence of the array. +""" + + +class Solution(object): + def findLengthOfShortestSubarray(self, arr): + """ + :type arr: List[int] + :rtype: int + """ + left, right = 0, len(arr) - 1 + while left < right and arr[left + 1] >= arr[left]: + left += 1 + if left == len(arr) - 1: + return 0 + while right > 0 and arr[right - 1] <= arr[right]: + right -= 1 + ans = min(len(arr) - left - 1, right) + for i in range(left + 1): + if arr[i] <= arr[right]: + ans = min(ans, right - i - 1) + elif right < len(arr) - 1: + right += 1 + else: + break + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findLengthOfShortestSubarray(arr=[1, 2, 3, 10, 4, 2, 3, 5])) + print(obj.findLengthOfShortestSubarray(arr=[5, 4, 3, 2, 1])) + print(obj.findLengthOfShortestSubarray(arr=[1, 2, 3])) |