1574. Shortest Subarray to be Removed to Make Array Sorted

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^5
• 0 <= 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/
// Author: github.com/lzl124631x
// 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;
    }
};