LeetCode 1574. Shortest Subarray to be Removed to Make Array Sorted Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

 

Constraints:

• 1 <= arr.length <= 105
• 0 <= arr[i] <= 109

Solutions

Solution 1: Two Pointers + Binary Search

First, we find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as nums[0..i] and nums[j..n-1], respectively.

If i ≥ j, it means the array is already non-decreasing, so we return 0.

Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is min(n - i - 1, j).

Next, we enumerate the right endpoint l of the left prefix. For each l, we can use binary search to find the first position greater than or equal to nums[l] in nums[j..n-1], denoted as r. At this point, we can delete nums[l+1..r-1] and update the answer ans = min(ans, r - l - 1). Continue enumerating l to get the final answer.

The time complexity is O(n × log n), where n is the length of the array. The space complexity is O(1).

PythonJavaC++Go

class Solution: def findLengthOfShortestSubarray(self, arr: List[int]) -> int: n = len(arr) i, j = 0, n - 1 while i + 1 < n and arr[i] <= arr[i + 1]: i += 1 while j - 1 >= 0 and arr[j - 1] <= arr[j]: j -= 1 if i >= j: return 0 ans = min(n - i - 1, j) for l in range(i + 1): r = bisect_left(arr, arr[l], lo=j) ans = min(ans, r - l - 1) return ans(code-box)

class Solution { public int findLengthOfShortestSubarray(int[] arr) { int n = arr.length; int i = 0, j = n - 1; while (i + 1 < n && arr[i] <= arr[i + 1]) { ++i; } while (j - 1 >= 0 && arr[j - 1] <= arr[j]) { --j; } if (i >= j) { return 0; } int ans = Math.min(n - i - 1, j); for (int l = 0; l <= i; ++l) { int r = search(arr, arr[l], j); ans = Math.min(ans, r - l - 1); } return ans; } private int search(int[] arr, int x, int left) { int right = arr.length; while (left < right) { int mid = (left + right) >> 1; if (arr[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; } }(code-box)

class Solution { public: int findLengthOfShortestSubarray(vector<int>& arr) { int n = arr.size(); int i = 0, j = n - 1; while (i + 1 < n && arr[i] <= arr[i + 1]) { ++i; } while (j - 1 >= 0 && arr[j - 1] <= arr[j]) { --j; } if (i >= j) { return 0; } int ans = min(n - 1 - i, j); for (int l = 0; l <= i; ++l) { int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin(); ans = min(ans, r - l - 1); } return ans; } };(code-box)

func findLengthOfShortestSubarray(arr []int) int { n := len(arr) i, j := 0, n-1 for i+1 < n && arr[i] <= arr[i+1] { i++ } for j-1 >= 0 && arr[j-1] <= arr[j] { j-- } if i >= j { return 0 } ans := min(n-i-1, j) for l := 0; l <= i; l++ { r := j + sort.SearchInts(arr[j:], arr[l]) ans = min(ans, r-l-1) } return ans }(code-box)

Solution 2: Two Pointers

Similar to Solution 1, we first find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as nums[0..i] and nums[j..n-1], respectively.

If i ≥ j, it means the array is already non-decreasing, so we return 0.

Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is min(n - i - 1, j).

Next, we enumerate the right endpoint l of the left prefix. For each l, we directly use two pointers to find the first position greater than or equal to nums[l] in nums[j..n-1], denoted as r. At this point, we can delete nums[l+1..r-1] and update the answer ans = min(ans, r - l - 1). Continue enumerating l to get the final answer.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

PythonJavaC++GoTypeScriptJavaScript

class Solution: def findLengthOfShortestSubarray(self, arr: List[int]) -> int: n = len(arr) i, j = 0, n - 1 while i + 1 < n and arr[i] <= arr[i + 1]: i += 1 while j - 1 >= 0 and arr[j - 1] <= arr[j]: j -= 1 if i >= j: return 0 ans = min(n - i - 1, j) r = j for l in range(i + 1): while r < n and arr[r] < arr[l]: r += 1 ans = min(ans, r - l - 1) return ans(code-box)

class Solution { public int findLengthOfShortestSubarray(int[] arr) { int n = arr.length; int i = 0, j = n - 1; while (i + 1 < n && arr[i] <= arr[i + 1]) { ++i; } while (j - 1 >= 0 && arr[j - 1] <= arr[j]) { --j; } if (i >= j) { return 0; } int ans = Math.min(n - i - 1, j); for (int l = 0, r = j; l <= i; ++l) { while (r < n && arr[r] < arr[l]) { ++r; } ans = Math.min(ans, r - l - 1); } return ans; } }(code-box)

class Solution { public: int findLengthOfShortestSubarray(vector<int>& arr) { int n = arr.size(); int i = 0, j = n - 1; while (i + 1 < n && arr[i] <= arr[i + 1]) { ++i; } while (j - 1 >= 0 && arr[j - 1] <= arr[j]) { --j; } if (i >= j) { return 0; } int ans = min(n - 1 - i, j); for (int l = 0, r = j; l <= i; ++l) { while (r < n && arr[r] < arr[l]) { ++r; } ans = min(ans, r - l - 1); } return ans; } };(code-box)

func findLengthOfShortestSubarray(arr []int) int { n := len(arr) i, j := 0, n-1 for i+1 < n && arr[i] <= arr[i+1] { i++ } for j-1 >= 0 && arr[j-1] <= arr[j] { j-- } if i >= j { return 0 } ans := min(n-i-1, j) r := j for l := 0; l <= i; l++ { for r < n && arr[r] < arr[l] { r += 1 } ans = min(ans, r-l-1) } return ans }(code-box)

function findLengthOfShortestSubarray(arr: number[]): number { let [l, r, n] = [0, arr.length - 1, arr.length]; while (r && arr[r - 1] <= arr[r]) r--; if (r === 0) return 0; let ans = r; while (l < r && (!l || arr[l - 1] <= arr[l])) { while (r < n && arr[l] > arr[r]) r++; ans = Math.min(ans, r - l - 1); l++; } return ans; }(code-box)

function findLengthOfShortestSubarray(arr) { let [l, r, n] = [0, arr.length - 1, arr.length]; while (r && arr[r - 1] <= arr[r]) r--; if (r === 0) return 0; let ans = r; while (l < r && (!l || arr[l - 1] <= arr[l])) { while (r < n && arr[l] > arr[r]) r++; ans = Math.min(ans, r - l - 1); l++; } return ans; }(code-box)