Skip to content

1574. Shortest Subarray to be Removed to Make Array Sorted 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int findLengthOfShortestSubarray(vector<int>& arr) {
    const int n = arr.size();
    int l = 0;
    int r = n - 1;

    // arr[0..l] is non-decreasing.
    while (l < n - 1 && arr[l + 1] >= arr[l])
      ++l;
    // arr[r..n - 1] is non-decreasing.
    while (r > 0 && arr[r - 1] <= arr[r])
      --r;
    // Remove arr[l + 1..n - 1] or arr[0..r - 1].
    int ans = min(n - 1 - l, r);

    // Since arr[0..l] and arr[r..n - 1] are non-decreasing, we place pointers
    // at the rightmost indices, l and n - 1, and greedily shrink them toward
    // the leftmost indices, 0 and r, respectively. By removing arr[i + 1..j],
    // we ensure that `arr` becomes non-decreasing.
    int i = l;
    int j = n - 1;
    while (i >= 0 && j >= r && j > i) {
      if (arr[i] <= arr[j])
        --j;
      else
        --i;
      ans = min(ans, j - i);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int findLengthOfShortestSubarray(int[] arr) {
    final int n = arr.length;
    int l = 0;
    int r = n - 1;

    // arr[0..l] is non-decreasing prefix.
    while (l < n - 1 && arr[l + 1] >= arr[l])
      ++l;
    // arr[r..n - 1] is non-decreasing suffix.
    while (r > 0 && arr[r - 1] <= arr[r])
      --r;
    // Remove arr[l + 1..n - 1] or arr[0..r - 1]
    int ans = Math.min(n - 1 - l, r);

    // Since arr[0..l] and arr[r..n - 1] are non-decreasing, we place pointers
    // at the rightmost indices, l and n - 1, and greedily shrink them toward
    // the leftmost indices, 0 and r, respectively. By removing arr[i + 1..j],
    // we ensure that `arr` becomes non-decreasing.
    int i = l;
    int j = n - 1;
    while (i >= 0 && j >= r && j > i) {
      if (arr[i] <= arr[j])
        --j;
      else
        --i;
      ans = Math.min(ans, j - i);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def findLengthOfShortestSubarray(self, arr: list[int]) -> int:
    n = len(arr)
    l = 0
    r = n - 1

    # arr[0..l] is non-decreasing.
    while l < n - 1 and arr[l + 1] >= arr[l]:
      l += 1
    # arr[r..n - 1] is non-decreasing.
    while r > 0 and arr[r - 1] <= arr[r]:
      r -= 1
    # Remove arr[l + 1..n - 1] or arr[0..r - 1].
    ans = min(n - 1 - l, r)

    # Since arr[0..l] and arr[r..n - 1] are non-decreasing, we place pointers
    # at the rightmost indices, l and n - 1, and greedily shrink them toward
    # the leftmost indices, 0 and r, respectively. By removing arr[i + 1..j],
    # we ensure that `arr` becomes non-decreasing.
    i = l
    j = n - 1
    while i >= 0 and j >= r and j > i:
      if arr[i] <= arr[j]:
        j -= 1
      else:
        i -= 1
      ans = min(ans, j - i)

    return ans