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^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/

// 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;
    }
}

All Problems

All Solutions