1574. Shortest Subarray Removed to Make Array Sorted

Problem Statement

Shortest Subarray to be Removed to Make Array Sorted - LeetCode

Pattern: Pattern Two Pointer

---

Solution

public int findLengthOfShortestSubarray(int[] arr) {
	// find lengths prefix and suffix subarray
	int left = 0, right = arr.length-1;
	
	while(left < right && arr[left+1] >= arr[left]) 
		left++;
	
	if (left == right) return 0;
			
	while(right > 0 && arr[right-1] <= arr[right])
		right--;
	
	// find smaller 'len'subarray 
	int minLength = Math.min(arr.length - left - 1, right);
	
	
	// find smallest 'len' sub, by merging prefix and suffix
	for (int i = 0, j = right ; i <= left ; i++) {
		
		// shift j fwds while arr[i] is larger
		while(j < arr.length && arr[i] > arr[j]) j++;
	
		if (j == arr.length) break;
		
		// update len
		minLength = Math.min(j - i - 1, minLength);
	}
	
	return minLength;
}

Notes

• Since we can only remove a subarray, the final remaining elements must be either: (1) solely a prefix, (2) solely a suffix or (3) a merge of the prefix and suffix.

1. Find the monotone non-decreasing prefix [a_0 ⇐ … a_i | …]
   • l is the index such that arr[l+1] < arr[l]
2. Find the monotone non-decreasing suffix [… | a_j ⇐ … a_n]
   • r is the index such that arr[r-1] > arr[r]
3. Try to “merge 2 sorted arrays”, if we can merge, update our minimum to remove.

• if the whole array is sorted, the ‘merging’ process might make the minLenth = -1 since j == i. So in that case we return if l == r