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.
1public class Solution {
2 public int findLengthOfShortestSubarray(int[] arr) {
3 int n = arr.length;
4 int left = 0, right = n - 1;
5
6 // Find first breaking point from the start
7 while (left < n - 1 && arr[left] <= arr[left + 1]) {
8 left++;
9 }
10
11 // Already sorted
12 if (left == n - 1) return 0;
13
14 // Find first breaking point from the end
15 while (right > 0 && arr[right - 1] <= arr[right]) {
16 right--;
17 }
18
19 // Minimum of removing left part or right part entirely
20 int result = Math.min(n - left - 1, right);
21
22 // Attempt to merge prefix and suffix
23 int i = 0, j = right;
24 while (i <= left && j < n) {
25 if (arr[i] <= arr[j]) {
26 result = Math.min(result, j - i - 1);
27 i++;
28 } else {
29 j++;
30 }
31 }
32
33 return result;
34 }
35
36 public static void main(String[] args) {
37 Solution sol = new Solution();
38 int[] arr = {1, 2, 3, 10, 4, 2, 3, 5};
39 System.out.println(sol.findLengthOfShortestSubarray(arr));
40 }
41}This Java solution follows the same logic as the Python solution, focusing on discovering the longest sorted segments from the start and end, then finds the minimal removal by aligning potential prefixes and suffixes.
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.