• Leetcode POTDs

Problem 1574 Shortest Subarray to be Removed to Make Array Sorted

Problem Statement

Link - Problem 1574

Question

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

Solution

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {

        int n = arr.size();
        int left = 0, right = n - 1;
        while(right > 0 && arr[right - 1] <= arr[right])
        {
            right--;
        }
        int ans = right;
        while(left < right && (left == 0 || arr[left - 1] <= arr[left]))
        {
            while(right < n && arr[left] > arr[right])
            {
                right++;
            }
            ans = min(ans, right - left - 1);
            left++;
        }
        return ans;
    }
};

Complexity Analysis

| Algorithm | Time Complexity | Space Complexity |
| --------- | --------------- | ---------------- |
| Greedy    | O(n)            | O(1)             |

Explanation

1. Intuition

• The problem asks us to find the length of the shortest subarray to remove from the given array such that the remaining elements are non-decreasing.
• We can approach this problem by finding the longest non-decreasing subarray and then subtracting its length from the total length of the array.
• We can use two pointers, one from the start and one from the end, to find the longest non-decreasing subarray.
• We can also use the fact that the longest non-decreasing subarray must end at the end of the array or start at the beginning of the array.

2. Implementation

• We initialize two pointers, left and right, to the start and end of the array respectively.
• We move the right pointer to the left until we find a pair of elements that are in non-decreasing order.
• We initialize the answer ans to the length of the subarray that we need to remove, which is right.
• We then move the left pointer to the right and for each position, we move the right pointer to the right until we find a pair of elements that are in non-decreasing order.
• We update the answer ans to be the minimum of the current answer and the length of the subarray that we need to remove, which is right - left - 1.
• We repeat this process until the left pointer is greater than or equal to the right pointer.
• Finally, we return the answer ans.

Complexity Analysis

Time Complexity:

• The algorithm consists of two while loops. The first loop runs at most n times (where n is the number of elements in the input array), because right starts at n - 1 and decrements
• The second loop also runs at most n times, because left starts at 0 and increments, and right starts at the index where the first loop ended
• Therefore, the total number of operations is proportional to n, giving the time complexity of O(n)
• This linear time complexity makes sense intuitively, as we’re scanning the input array from left to right

Space Complexity:

• No additional space is used that scales with the input size. We only use a constant amount of space to store the left, right, ans, and n variables
• This gives us a space complexity of O(1), because the used space does not grow with the input size

Footnote

This question is rated as Medium difficulty.

Hints

The key is to find the longest non-decreasing subarray starting with the first element or ending with the last element, respectively.

After removing some subarray, the result is the concatenation of a sorted prefix and a sorted suffix, where the last element of the prefix is smaller than the first element of the suffix.

Similar Questions: