1574. Shortest Subarray to be Removed to Make Array Sorted

[mah-shamim]

Topics: Array, Two Pointers, Binary Search, Stack, Monotonic Stack

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

Hint:

1. The key is to find the longest non-decreasing subarray starting with the first element or ending with the last element, respectively.
2. 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.

[mah-shamim]

We can use sorting and binary search techniques. Here’s the plan:

Approach:

1. Two Pointers Approach:

   • First, identify the longest non-decreasing prefix (left pointer).
   • Then, identify the longest non-decreasing suffix (right pointer).
   • After that, try to combine these two subarrays by considering the middle part of the array and adjusting the subarray to be removed in such a way that the combined array is non-decreasing.

2. Monotonic Stack:

   • Use a monotonic stack to help manage subarray elements in a sorted fashion.

3. Steps:

   • Find the longest non-decreasing prefix (left).
   • Find the longest non-decreasing suffix (right).
   • Try to merge the two subarrays by looking for elements that can form a valid combination.

4. Optimization:

   • Use binary search to optimize the merging step for finding the smallest subarray to remove.

Let's implement this solution in PHP: 1574. Shortest Subarray to be Removed to Make Array Sorted

<?php
/**
 * @param Integer[] $arr
 * @return Integer
 */
function shortestSubarrayToRemove($arr) {
    $n = count($arr);
    
    // Find the longest non-decreasing prefix
    $left = 0;
    while ($left < $n - 1 && $arr[$left] <= $arr[$left + 1]) {
        $left++;
    }
    
    // If the entire array is sorted
    if ($left == $n - 1) {
        return 0;
    }
    
    // Find the longest non-decreasing suffix
    $right = $n - 1;
    while ($right > 0 && $arr[$right - 1] <= $arr[$right]) {
        $right--;
    }
    
    // Minimum removal when keeping only the prefix or suffix
    $minRemove = min($n - $left - 1, $right);
    
    // Try to merge prefix and suffix
    $i = 0;
    $j = $right;
    while ($i <= $left && $j < $n) {
        if ($arr[$i] <= $arr[$j]) {
            $minRemove = min($minRemove, $j - $i - 1);
            $i++;
        } else {
            $j++;
        }
    }
    
    return $minRemove;
}

// Test cases
echo shortestSubarrayToRemove([1, 2, 3, 10, 4, 2, 3, 5]) . "\n"; // Output: 3
echo shortestSubarrayToRemove([5, 4, 3, 2, 1]) . "\n";           // Output: 4
echo shortestSubarrayToRemove([1, 2, 3]) . "\n";                 // Output: 0
?>

Explanation:

1. Longest Non-Decreasing Prefix and Suffix:

   • The prefix is determined by traversing the array from the start until elements are in non-decreasing order.
   • Similarly, the suffix is determined by traversing from the end.

2. Initial Minimum Removal:

   • Calculate the removal length by keeping only the prefix or the suffix.

3. Merging Prefix and Suffix:

   • Use two pointers (i for prefix and j for suffix) to find the smallest subarray to remove such that the last element of the prefix is less than or equal to the first element of the suffix.

4. Return Result:

   • The result is the minimum length of the subarray to remove, calculated as the smaller of the initial removal or the merging of prefix and suffix.

Complexity

• Time Complexity: O(n), as the array is traversed at most twice.
• Space Complexity: O(1), as only a few variables are used.

This solution efficiently finds the shortest subarray to be removed to make the array sorted by using a two-pointer technique, and it handles large arrays up to the constraint of 10^5 elements.

[kovatz]

Thanks to solve the "Shortest Subarray to be Removed to Make Array Sorted" problem

[mah-shamim]

Thanks