1574 - Shortest Subarray to be Removed to Make Array Sorted

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

C++

• class Solution {
  public:
      int findLengthOfShortestSubarray(vector<int>& arr) {
          int n = arr.size();
          int i = 0, j = n - 1;
          while (i + 1 < n && arr[i] <= arr[i + 1]) {
              ++i;
          }
          while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
              --j;
          }
          if (i >= j) {
              return 0;
          }
          int ans = min(n - 1 - i, j);
          for (int l = 0; l <= i; ++l) {
              int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin();
              ans = min(ans, r - l - 1);
          }
          return ans;
      }
  };

JAVA

• class Solution {
      public int findLengthOfShortestSubarray(int[] arr) {
          int n = arr.length;
          int i = 0, j = n - 1;
          while (i + 1 < n && arr[i] <= arr[i + 1]) {
              ++i;
          }
          while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
              --j;
          }
          if (i >= j) {
              return 0;
          }
          int ans = Math.min(n - i - 1, j);
          for (int l = 0; l <= i; ++l) {
              int r = search(arr, arr[l], j);
              ans = Math.min(ans, r - l - 1);
          }
          return ans;
      }
  
      private int search(int[] arr, int x, int left) {
          int right = arr.length;
          while (left < right) {
              int mid = (left + right) >> 1;
              if (arr[mid] >= x) {
                  right = mid;
              } else {
                  left = mid + 1;
              }
          }
          return left;
      }
  }

PYTHON

• from bisect import bisect_left
  
  class Solution:
      def findLengthOfShortestSubarray(self, arr):
          n = len(arr)
          i, j = 0, n - 1
  
          while i + 1 < n and arr[i] <= arr[i + 1]:
              i += 1
  
          while j - 1 >= 0 and arr[j - 1] <= arr[j]:
              j -= 1
  
          if i >= j:
              return 0
  
          ans = min(n - 1 - i, j)
  
          for l in range(i + 1):
              r = bisect_left(arr, arr[l], j, n)
              ans = min(ans, r - l - 1)
  
          return ans