Sponsored
Sponsored
This 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.
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.
1def findLengthOfShortestSubarray(arr):
2 n = len(arr)
3 left, right = 0, n - 1
4
5 # Find the first breaking point from the start
6 while left < n - 1 and arr[left] <= arr[left + 1]:
7 left += 1
8
9 # If the array is already non-decreasing
10 if left == n - 1:
11 return 0
12
13 # Find the first breaking point from the end
14 while right > 0 and arr[right - 1] <= arr[right]:
15 right -= 1
16
17 # Result can be either removing one of the segments entirely
18 result = min(n - left - 1, right)
19
20 # Combine a valid prefix and suffix
21 i, j = 0, right
22 while i <= left and j < n:
23 if arr[i] <= arr[j]:
24 result = min(result, j - i - 1)
25 i += 1
26 else:
27 j += 1
28
29 return result
30
31# Example usage:
32arr = [1, 2, 3, 10, 4, 2, 3, 5]
33print(findLengthOfShortestSubarray(arr))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.
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.
Time complexity: O(n log n), due to the binary search operations.
Space complexity: O(1).
1import bisect
2
3def
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.