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 <= 1050 <= arr[i] <= 109This approach uses two pointers to identify the first breaking point from both ends of the array and then calculates the minimum subarray length to remove by exploring combinations that can join two sorted parts.
Initialize two pointers, left starting from index 0 and right starting from the last index. First, traverse from the start until you find a break in the non-decreasing order to mark the left boundary. Similarly, traverse from the end to find the right boundary where a decrease occurs compared to the previous element.
Once both pointers are positioned correctly, slide the left pointer through the possible combinations and find the smallest subarray that can be removed to make the rest of the array sorted.
The above code first finds the longest non-decreasing subarray from the start and end of the array using two pointers, left and right. After determining these points, it attempts to merge these sorted segments by sliding through potential combinations and returns the minimal length of the subarray to be removed.
Java
Time complexity: O(n), where n is the length of the array since we traverse the array twice with additional O(n) operations.
Space complexity: O(1), as no extra space is used, except for a few variables.
This approach leverages binary search to efficiently find the optimal 'join point' between a sorted prefix and suffix. By keeping track of sorted segments from both ends, binary search is used to quickly determine the minimum subarray to remove by checking suitable merge points.
First, determine the lengths of sorted segments from the beginning and end. Then, use binary search to identify an index where blending the end and start segments maintains the non-decreasing order.
This implementation identifies sorted prefix and suffix ranges and uses binary search to determine the minimal join point. It calculates and returns the smallest segment required for removal to satisfy the sorted property of the remaining array.
C++
Time complexity: O(n log n), due to the binary search operations.
Space complexity: O(1).
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time complexity: O(n), where n is the length of the array since we traverse the array twice with additional O(n) operations. |
| Binary Search for Optimal Join Point | Time complexity: O(n log n), due to the binary search operations. |
Shortest Subarray to be Removed to Make Array Sorted - Leetcode 1574 - Python • NeetCodeIO • 12,519 views views
Watch 9 more video solutions →Practice Shortest Subarray to be Removed to Make Array Sorted with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor