Formatted question description: https://leetcode.ca/all/1574.html
1574. Shortest Subarray to be Removed to Make Array Sorted (Medium)
Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
A subarray is a contiguous subsequence of the array.
Return the length of the shortest subarray to remove.
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.
Example 4:
Input: arr = [1] Output: 0
Constraints:
1 <= arr.length <= 10^50 <= arr[i] <= 10^9
Related Topics:
Array, Binary Search
Solution 1. Two Pointers
Scan from left to right, find the first index left that A[left] > A[left + 1].
If left == N - 1, this array is already non-descending, return 0.
Scan from right to left, find the first index right that A[right] < A[right - 1].
Now we loosely have two options, either deleting the left-side right nodes, or deleting the right-side N - left - 1 nodes.
So the answer is at most min(N - left - 1, right).
Now we can use a sliding window / two pointers to get tighter result.
Let i = 0, j = right. And we examine if we can delete elements between i and j (exclusive) by comparing A[i] and A[j].
Case 1: A[j] >= A[i], we can delete elements inbetween, so we can try to update the answer using j - i - 1 and increment i to tighten the window.
Case 2: A[j] < A[i], we can’t delete elements inbetween, so we increment j to loosen the window.
We loop until i > left or j == N. And the answer we get should be the minimal possible solution.
// OJ: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/830416/Java-Increasing-From-Left-Right-and-Merge-O(n)
class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& A) {
int N = A.size(), left = 0, right = N - 1;
while (left + 1 < N && A[left] <= A[left + 1]) ++left;
if (left == N - 1) return 0;
while (right > left && A[right - 1] <= A[right]) --right;
int ans = min(N - left - 1, right), i = 0, j = right;
while (i <= left && j < N) {
if (A[j] >= A[i]) {
ans = min(ans, j - i - 1);
++i;
} else ++j;
}
return ans;
}
};
Java
class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
boolean flag = true;
int length = arr.length;
for (int i = 1; i < length; i++) {
if (arr[i] < arr[i - 1]) {
flag = false;
break;
}
}
if (flag)
return 0;
int minLength = length - 1;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(length - 1);
for (int i = length - 2; i >= 0; i--) {
int num = arr[i];
if (num <= arr[stack.peek()])
stack.push(i);
else
break;
}
for (int i = 0; i < length; i++) {
int num = arr[i];
if (i > 0 && num < arr[i - 1])
break;
while (!stack.isEmpty() && num > arr[stack.peek()])
stack.pop();
int next = stack.isEmpty() ? length : stack.peek();
minLength = Math.min(minLength, next - i - 1);
}
stack.clear();
stack.push(0);
for (int i = 1; i < length; i++) {
int num = arr[i];
if (num >= arr[stack.peek()])
stack.push(i);
else
break;
}
for (int i = length - 1; i >= 0; i--) {
int num = arr[i];
if (i < length - 1 && num > arr[i + 1])
break;
while (!stack.isEmpty() && num < arr[stack.peek()])
stack.pop();
int prev = stack.isEmpty() ? -1 : stack.peek();
minLength = Math.min(minLength, i - prev - 1);
}
return minLength;
}
}