1574. Shortest Subarray to be Removed to Make Array Sorted
Problem Description
The goal is to find the minimum length of a subarray that, when removed from an array arr
, leaves the remaining elements in a non-decreasing order (i.e., each element is less than or equal to the next). In other words, after removing the subarray, the resulting array should be sorted in non-decreasing order. This problem also includes the possibility of not removing any subarray at all if arr
is already non-decreasing. The term "subarray" refers to a sequence of elements that are contiguous within the arr
.
Intuition
The key to solving this problem lies in identifying parts of the array that are already sorted in non-decreasing order. Once we've identified such parts, we can find the minimum subarray to be removed. The solution approach can be broken down into the following steps:
- Find the longest non-decreasing subarray from the start (
left
sorted subarray). - Find the longest non-decreasing subarray from the end (
right
sorted subarray). - Evaluate if the entire array is already non-decreasing by checking if the
left
andright
overlap or touch each other. If they do, the shortest subarray to remove would be of length 0, which means we don't have to remove anything. - If a removal is needed, we can consider two potential solutions:
- Remove the elements from the end of the
left
sorted subarray to the beginning of the array, leaving only theright
sorted subarray. - Remove the elements from the start of the
right
sorted subarray to the end of the array, leaving only theleft
sorted subarray.
- Remove the elements from the end of the
- It's possible that by combining some portion of the
left
subarray with some portion of theright
subarray, we could actually remove a shorter subarray in between and still maintain the non-decreasing order. Therefore, we iterate through theleft
sorted subarray and try to match its end with the beginning of theright
sorted subarray, minimizing the length of the subarray to be removed.
Following these steps, we can determine the shortest subarray to remove, ensuring the array remains sorted in non-decreasing order after the removal.
Learn more about Stack, Two Pointers, Binary Search and Monotonic Stack patterns.
Solution Approach
The solution approach consists of several key steps that use loops and variables to track the progress through the array arr
. Here's how the implementation works:
- Initialize two pointers,
i
at the beginning of the array andj
at the end. These pointers are used to find theleft
andright
sorted subarrays, respectively. - Progress
i
forward through the array until we find the first element that is not in non-decreasing order. Until that point, the elements rest in a sorted subarray from the start. - Similarly, move
j
backwards through the array to find the first element from the end that breaks the non-decreasing order. Until that point, the elements are in a sorted subarray from the end. - If
i
has passedj
, return 0, as the entire array is already non-decreasing or it has only one element that is out of order, which can be removed by itself. - Compute the initial potential answers:
- The length of a subarray from
i
to the end of the array:n - i - 1
- The length of a subarray from the start of the array to
j
:j
- The length of a subarray from
- Then comes the crucial step: trying to find the shortest subarray for removal that possibly lies between the sorted subarrays identified in steps 2 and 3. Initialize a new pointer
r
(short for right) toj
. - Now, iterate through the array
arr
using theleft
pointer from 0 toi
(inclusive). For each position of theleft
pointer, progress theright
pointer untilarr[r]
is not less thanarr[l]
, ensuring that elements to the left and right are in non-decreasing order. - Update answer
ans
each time to reflect the minimal value: the currentans
and the number of elements between theleft
andright
pointers, denoted byr - l - 1
.
By following these steps, the function concludes by returning ans
, which represents the length of the shortest subarray to remove to achieve a non-decreasing array after its removal.
This implementation is efficient and makes clever use of two-pointer technique along with a simple for
loop and while loop constructs to keep track of the non-decreasing subarrays from both the start and end of the input array and to calculate the minimum length of the subarray that needs to be removed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the array arr = [1, 3, 2, 3, 5]
.
- Starting from the left, we see that
1 <= 3
, but3 > 2
, so the longest non-decreasing subarray from the start is[1, 3]
withi = 1
. - Starting from the right, we see that
5 >= 3
,3 >= 2
, but2 < 3
, so the longest non-decreasing subarray from the end is[2, 3, 5]
withj = 2
. - Since
i < j
, they do not overlap, and we must remove a subarray to make the entire array non-decreasing. - If we remove elements starting from the end of the
left
sorted subarray to the beginning of the array, we would remove[1, 3]
, leaving[2, 3, 5]
, which is in non-decreasing order. However, this results in removing 2 elements. - Conversely, if we remove elements from the start of the
right
sorted subarray to the end of the array, we would remove[3, 5]
, leaving[1, 3, 2]
, which is not in non-decreasing order, so this is not a valid option. - Now, we check to see if it's possible to maintain a part of the
left
subarray[1, 3]
and combine it with theright
subarray[2, 3, 5]
to minimize the length of the subarray to be removed. To find the shortest subarray for removal, initialize pointerr
(short for right) toj
, which is 2 at the moment. - We iterate through the array from the left pointer
l = 0
toi = 1
. Whenl = 0
,arr[l] = 1
is less thanarr[r] = 2
(sincer
is atj
), so we don't need to mover
. Next, whenl = 1
,arr[l] = 3
is greater thanarr[r] = 2
, so we incrementr
to ensure thatarr[r]
is not less thanarr[l]
. Sincearr[r] = 3
is now greater thanarr[l] = 3
, we can stop. - The minimal length of the subarray to be removed lies in between pointer
l
and pointerr
, which in this case is the subarray[2]
(sincer = 3
andl = 1
, we haver - l - 1 = 3 - 1 - 1 = 1
element to be removed).
Thus, by following the solution steps, the smallest subarray we need to remove to make arr
sorted in non-decreasing order is [2]
of length 1. Hence, the function returns 1 as the answer.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
5 # Length of the array
6 length = len(arr)
7
8 # Initialize two pointers for the beginning and end of the array
9 left = 0
10 right = length - 1
11
12 # Move the left pointer to the right as long as the subarray is non-decreasing
13 while left + 1 < length and arr[left] <= arr[left + 1]:
14 left += 1
15
16 # Move the right pointer to the left as long as the subarray is non-decreasing
17 while right - 1 >= 0 and arr[right - 1] <= arr[right]:
18 right -= 1
19
20 # If the whole array is already non-decreasing, return 0
21 if left >= right:
22 return 0
23
24 # Calculate the length of the remaining array to be removed
25 min_length_to_remove = min(length - left - 1, right)
26
27 # Reinitialize the right pointer for the next loop
28 new_right = right
29
30 # Check for the shortest subarray from the left side to the midpoint
31 for new_left in range(left + 1):
32 # Increment the right pointer until the elements on both sides are non-decreasing
33 while new_right < length and arr[new_right] < arr[new_left]:
34 new_right += 1
35 # Update the minimum length if a shorter subarray is found
36 min_length_to_remove = min(min_length_to_remove, new_right - new_left - 1)
37
38 # Return the minimum length of the subarray to remove to make array non-decreasing
39 return min_length_to_remove
40
1class Solution {
2 public int findLengthOfShortestSubarray(int[] arr) {
3 int n = arr.length;
4 // Find the length of the non-decreasing starting subarray.
5 int left = 0, right = n - 1;
6 while (left + 1 < n && arr[left] <= arr[left + 1]) {
7 left++;
8 }
9 // If the whole array is already non-decreasing, return 0.
10 if (left == n - 1) {
11 return 0;
12 }
13
14 // Find the length of the non-decreasing ending subarray.
15 while (right > 0 && arr[right - 1] <= arr[right]) {
16 right--;
17 }
18
19 // Compute the length of the subarray to be removed,
20 // considering only one side (either starting or ending subarray).
21 int minLengthToRemove = Math.min(n - left - 1, right);
22
23 // Try to connect a prefix of the starting non-decreasing subarray
24 // with a suffix of the ending non-decreasing subarray.
25 for (int leftIdx = 0, rightIdx = right; leftIdx <= left; leftIdx++) {
26 // Move the rightIdx pointer to the right until we find an element
27 // that is not less than the current element from the left side.
28 while (rightIdx < n && arr[rightIdx] < arr[leftIdx]) {
29 rightIdx++;
30 }
31 // Update the answer with the minimum length found so far.
32 minLengthToRemove = Math.min(minLengthToRemove, rightIdx - leftIdx - 1);
33 }
34 return minLengthToRemove;
35 }
36}
37
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int findLengthOfShortestSubarray(std::vector<int>& arr) {
7 int n = arr.size(); // The size of the input array
8 int left = 0, right = n - 1; // Pointers to iterate through the array
9
10 // Expand the left pointer as long as the current element is smaller or equal than the next one
11 // This means the left part is non-decreasing
12 while (left + 1 < n && arr[left] <= arr[left + 1]) {
13 ++left;
14 }
15
16 // If the whole array is non-decreasing, no removal is needed
17 if (left == n - 1) {
18 return 0;
19 }
20
21 // Expand the right pointer inwards as long as the next element leftwards is smaller or equal
22 // This means the right part is non-decreasing
23 while (right > 0 && arr[right - 1] <= arr[right]) {
24 --right;
25 }
26
27 // Calculate the initial length of the subarray that we can potentially remove
28 int minSubarrayLength = std::min(n - left - 1, right);
29
30 // Attempt to merge the non-decreasing parts on the left and the right
31 for (int l = 0, r = right; l <= left; ++l) {
32 // Find the first element which is not less than arr[l] in the right part to merge
33 while (r < n && arr[r] < arr[l]) {
34 ++r;
35 }
36 // Update the answer with the minimum length after merging
37 minSubarrayLength = std::min(minSubarrayLength, r - l - 1);
38 }
39
40 // Return the answer which is the length of the shortest subarray to remove
41 return minSubarrayLength;
42 }
43};
44
1function findLengthOfShortestSubarray(arr: number[]): number {
2 const n: number = arr.length; // The size of the input array
3 let left: number = 0; // Pointer to iterate from the start
4 let right: number = n - 1; // Pointer to iterate from the end
5
6 // Expand the left pointer as long as the current element is smaller than or equal to the next one
7 // This means the left part is non-decreasing
8 while (left + 1 < n && arr[left] <= arr[left + 1]) {
9 left++;
10 }
11
12 // If the whole array is non-decreasing, no removal is needed
13 if (left === n - 1) {
14 return 0;
15 }
16
17 // Expand the right pointer inward as long as the next element to the left is smaller than or equal
18 // This means the right part is non-decreasing
19 while (right > 0 && arr[right - 1] <= arr[right]) {
20 right--;
21 }
22
23 // Calculate the initial length of the subarray that we can potentially remove
24 let minSubarrayLength: number = Math.min(n - left - 1, right);
25
26 // Attempt to merge the non-decreasing parts on the left and the right
27 for (let l: number = 0, r: number = right; l <= left; l++) {
28 // Find the first element which is not less than arr[l] in the right part to merge
29 while (r < n && arr[r] < arr[l]) {
30 r++;
31 }
32 // Update the minimum length after merging
33 minSubarrayLength = Math.min(minSubarrayLength, r - l - 1);
34 }
35
36 // Return the minimum length, which is the length of the shortest subarray to remove
37 return minSubarrayLength;
38}
39
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be broken down as follows:
- Two while loops (before the
if
statement) are executed sequentially, each advancing at mostn
steps. The worst-case complexity for this part is O(n
). - The
if
statement is a constant time check O(1). - The minimum of
n - i - 1
andj
is also a constant time operation O(1). - A for loop runs from
0
toi + 1
, and inside it, there is a while loop that could iterate fromj
ton
in the worst case. In the worst-case scenario, this nested loop could run O(n
^2) times because for each iteration of the for loop (at mostn
times), the while loop could also iteraten
times.
Thus, the overall time complexity is dominated by the nested loop, giving us a worst-case time complexity of O(n
^2).
Space Complexity
The space complexity is determined by the extra space used by the algorithm besides the input. In this case:
- Variables
i
,j
,n
,ans
, andr
use constant space O(1). - There are no additional data structures used that grow with the size of the input.
Therefore, the space complexity is O(1), which corresponds to constant space usage.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.