aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--shortest_subarr_remove_sort.c37
-rw-r--r--shortest_subarr_remove_sort.py39
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]))