diff options
-rw-r--r-- | shortest_subarr_remove_sort.c | 37 | ||||
-rw-r--r-- | shortest_subarr_remove_sort.py | 39 |
2 files changed, 76 insertions, 0 deletions
diff --git a/shortest_subarr_remove_sort.c b/shortest_subarr_remove_sort.c new file mode 100644 index 0000000..41ffa20 --- /dev/null +++ b/shortest_subarr_remove_sort.c @@ -0,0 +1,37 @@ +// 1574. Shortest Subarray to be Removed to Make Array Sorted +#include "leetcode.h" + +/* + * 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. + */ + +int findLengthOfShortestSubarray(int *arr, int arrSize) { + int left = 0, right = arrSize - 1; + while (left + 1 < arrSize && arr[left] <= arr[left + 1]) + left++; + if (left == arrSize - 1) + return 0; + while (right > left && arr[right - 1] <= arr[right]) + right--; + int ans = arrSize - left - 1 < right ? arrSize - left - 1 : right; + int i = 0, j = right; + while (i <= left && j < arrSize) { + if (arr[j] >= arr[i]) { + ans = ans < j - i - 1 ? ans : j - i - 1; + i++; + } else + j++; + } + return ans; +} + +int main() { + int a1[] = {1, 2, 3, 10, 4, 2, 3, 5}, a2[] = {5, 4, 3, 2, 1}, + a3[] = {1, 2, 3}; + printf("%d\n", findLengthOfShortestSubarray(a1, ARRAY_SIZE(a1))); // expect: 3 + printf("%d\n", findLengthOfShortestSubarray(a2, ARRAY_SIZE(a2))); // expect: 4 + printf("%d\n", findLengthOfShortestSubarray(a3, ARRAY_SIZE(a3))); // expect: 0 +} 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])) |