Min subarray remove to make array sorted #medium #two_pointers
Intuition
(Failed)
There are only 3 possibilities:
remove from the start
remove from the end
remove from the center
How to optimally remove from the center?
(At this point I've used all the hints and gave up)
For example: 1 2 3 4 1 1 3 2 3 4 5 6 Take prefix until it is sorted 1 2 3 4. Take suffix until it is sorted 2 3 4 5 6. Now we have to optimally overlap it:
So, we have to search though all possible overlaps and peek the best result.
(What was hard for me is to arrive to how exactly search all possible overlaps, my attempt to decrease left and increase right pointers was wrong)
The optimal way to do this is to scan both prefix and suffix from the start, always increasing the smallest one.
Approach
micro-optimization: we can find prefix in the same loop as the main search
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$
Code
fun findLengthOfShortestSubarray(arr: IntArray): Int {
var h = arr.lastIndex; var l = 0
while (h > 0 && arr[h - 1] <= arr[h]) h--
var res = h
while (l < h && h <= arr.size && (l < 1 || arr[l] >= arr[l - 1]))
if (h == arr.size || arr[l] <= arr[h])
res = min(res, h - l++ - 1) else h++
return res
}
pub fn find_length_of_shortest_subarray(arr: Vec<i32>) -> i32 {
let n = arr.len(); let (mut l, mut h) = (0, n - 1);
while h > 0 && arr[h - 1] <= arr[h] { h -= 1 }
let mut res = h;
while l < h && h <= n && (l < 1 || arr[l] >= arr[l - 1]) {
if h == n || arr[l] <= arr[h] {
res = res.min(h - l - 1); l += 1
} else { h += 1 }
}; res as i32
}
int findLengthOfShortestSubarray(vector<int>& arr) {
int n = arr.size(), h = n - 1, res, l = 0;
while (h > 0 && arr[h - 1] <= arr[h]) h--;
for (res = h; l < h && h <= n && (l < 1 || arr[l] >= arr[l - 1]);)
h == n || arr[l] <= arr[h] ? res = min(res, h - l++ - 1) : h++;
return res;
}
