Scale Engineer

Shortest Subarray to be Removed to Make Array Sorted

Med
#1448Time: O(N^3), where N is the number of elements in the array. The two nested loops for `i` and `j` result in O(N^2) pairs. For each pair, creating and checking the temporary array takes O(N) time.Space: O(N), where N is the number of elements in the array. This is because in each iteration, a temporary list of size up to N is created to check for sortedness.2 companies
Patterns
Two Pointers
Algorithms
Binary Search
Data structures
ArrayStackMonotonic Stack
Companies
DE Shawrazorpay

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves trying every possible contiguous subarray for removal. For each potential subarray removal, we construct the remaining array and check if it is sorted in non-decreasing order. We keep track of the length of the shortest subarray that results in a sorted array.

Algorithm

  • Initialize minLength to n, the maximum possible length to remove.
  • Use a nested loop to iterate through all possible start indices i (from 0 to n) and end indices j (from i to n) of a subarray to be removed.
  • For each pair (i, j), the subarray arr[i...j-1] is considered for removal.
  • Create a temporary list by concatenating the prefix arr[0...i-1] and the suffix arr[j...n-1].
  • Iterate through the temporary list to check if it is sorted in non-decreasing order.
  • If the list is sorted, update minLength with the length of the removed subarray, which is j - i.
  • After checking all possibilities, return minLength.

Walkthrough

The most straightforward way to solve the problem is to consider every single subarray that could be removed. We can define a subarray to be removed by its start and end indices. Let's say we remove the subarray arr[i...j-1]. The remaining parts of the array are the prefix arr[0...i-1] and the suffix arr[j...n-1]. We can form a new array by combining these two parts and then check if this new array is sorted. We do this for all possible i and j and keep track of the minimum length j - i that yields a sorted array.

class Solution {    public int findLengthOfShortestSubarray(int[] arr) {        int n = arr.length;        int minLength = n - 1;         // i is the start of the removed subarray        // j is the end of the removed subarray + 1        for (int i = 0; i <= n; i++) {            for (int j = i; j <= n; j++) {                java.util.List<Integer> temp = new java.util.ArrayList<>();                for (int k = 0; k < i; k++) {                    temp.add(arr[k]);                }                for (int k = j; k < n; k++) {                    temp.add(arr[k]);                }                 boolean isSorted = true;                for (int k = 0; k < temp.size() - 1; k++) {                    if (temp.get(k) > temp.get(k + 1)) {                        isSorted = false;                        break;                    }                }                 if (isSorted) {                    minLength = Math.min(minLength, j - i);                }            }        }        return minLength;    }}

Complexity

Time

O(N^3), where N is the number of elements in the array. The two nested loops for `i` and `j` result in O(N^2) pairs. For each pair, creating and checking the temporary array takes O(N) time.

Space

O(N), where N is the number of elements in the array. This is because in each iteration, a temporary list of size up to N is created to check for sortedness.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem for small inputs.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.

  • Uses extra space proportional to the input size in each iteration.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem