- The array is already sorted. (Important to check this condition)
Input: [1, 2, 3]
Output: 0
- The array is in descending order.
Input: [3, 2, 1]
Output: 2
For a given array, we can breakdown into three parts:
[X X X X] [Y Y Y Y] [Z Z Z Z]
0 i j n-1To make the whole array sorted by removing Y part (may be empty), we have to satisfy the following conditions:
[0:i]is non-decreasing.[j:n-1]is non-decreasing.arr[i] <= arr[j].
So the first steps is to identify the longest non-decreasing subarrays from the beginning and the end of the array. (for the conditions 1. and 2. above)
For the example input [1, 2, 3, 9, 4, 2, 3, 5], we can identify the two non-decreasing subarrays from the beginning and the end of the array:
[1, 2, 3, 9, 4, 2, 3, 5]
^^^^^^^^^^
L
[1, 2, 3, 9, 4, 2, 3, 5]
^^^^^^^
RAfter identifying the longest non-decreasing subarray from the beginning and the end, there are 3 options to consider as the result:
- We remove the left part:
[X, X, X, X, X, 2, 3, 5] - We remove the right part:
[1, 2, 3, 9, X, X, X, X] - We remove the middle part and merge the two non-decreasing subarrays into one:
[1, 2, 3, 9, 2, 3, 5]
We can initialize our result as the minimum of the two options 1 and 2, then we consider the third option: to merge the two subarrays into one, but it is not guaranteed that the merged array is sorted.
fun findLengthOfShortestSubarray(arr: IntArray): Int {
var n = arr.size
var left = 0
// Find the longest non-decreasing subarray from the beginning
while (left + 1 < n && arr[left] <= arr[left + 1]) left++
// All are non-decreasing (it's necessary to check this condition)
if (left == n - 1) return 0
// Find the longest non-decreasing subarray from the end
var right = n - 1
while (0 <= right - 1 && arr[right - 1] <= arr[right]) right--
// Remove left part or right part
var result = minOf(n - left - 1, right)
// TODO: Not finished, see below...
}Next question is how to delete the minimum number of elements to make the merged array sorted?
1, 2, 3, 9, 2, 3, 5
<-- L R -->How to move the pointers L and R?
Very nice illustration to explain how to move the pointers
LandR: https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/solutions/2189149/dong-hua-yi-xie-jiu-cuo-liang-chong-xie-iijwz/
Since the R..n-1 is non-decreasing (sorted), so we can iterate all possible l in 0..L, then binary search the first r in R..n-1 that satisfies arr[l] <= arr[r] (keep sorted after merge):
[0, ... L], ..., [R, ... n-1]
l -> r ->0 1 2 3 4 5 6 7 // index
1, 2, 3, 9, 2, 3, 5 // value
L R // the original non-decreasing subarrays
|--------| |--------|
l r // l = 0 -> r = 4, to remove is 3 (2, 3, 9)
l r // l = 1 -> r = 4, to remove is 2 (3, 9)
l r // l = 2 -> r = 5, to remove is 1 (9, 2)
l r // r is out of range, to remove is 3 (2, 3, 5)fun findLengthOfShortestSubarray(arr: IntArray): Int {
// ... see above
for (l in 0..left) {
// right is monotonic increasing, so we don't start from original right index
right = search(arr, arr[l], right)
result = minOf(result, right - l - 1)
}
return result
}
private fun search(arr: IntArray, target: Int, startIndex: Int): Int {
var left = startIndex
var right = arr.size - 1
while (left <= right) {
val middle = left + (right - left) / 2
if (target <= arr[middle]) {
right = middle - 1
} else {
left = middle + 1
}
}
return left
}- Time Complexity:
O(n log n) - Space Complexity:
O(1)
We can optimize the above solution based on the same idea (to find the first r that satisfies arr[l] <= arr[r]) by using two pointers approach.
Because 0..L and R..n-1 are both non-decreasing, as we find the first r that satisfies arr[l] <= arr[r] in the first iteration, then we can start from the previous r to find the next r that satisfies arr[l] <= arr[r], we don't need to start from R again.
1, 3, 8, 9, 2, 3, 5, 6, 7, 8
L R
|--------| |--------------|
l r1 // first iteration
l ->r2 // second iteration, r starts from the previous r
l r2 -------> r3 // third iteration
l r3 -> As we move l and r in the same direction, rather than starting from R again, we can find the next r that satisfies arr[l] <= arr[r] in O(n) time complexity.
因为i的移动必须保证
[0:i]单调增，所以arr[i]会变大，所以arr[j]必然也要增大以保证arr[j]>=arr[i]。我们还发现[j:n-1]也是单调增的区间，所以我们必然会将j右移。这样我们会找到下一个合适的j，使得此时的{i,j}成为一组合适的解。同理的分析，我们每向右移动一次i指针，必然也必须向右移动
j指针以寻找合适的{i,j}。这就是一个双指针的模式。所以我们用o(n)的时间复杂度就可以探索到所有合适的{i,j}.
fun findLengthOfShortestSubarray(arr: IntArray): Int {
// ... see above
var l = 0
var r = right
while (l <= left && r < n) {
if (arr[l] <= arr[r]) {
result = minOf(result, r - l - 1)
l++
// We don't update r here, r should be the previous r
} else {
r++
}
}
return result
}- Time Complexity:
O(n) - Space Complexity:
O(1)
[1,2,3,10,0,7,8,9] should return 2, but my code returns 4.
fun findLengthOfShortestSubarray(arr: IntArray): Int {
var n = arr.size
var left = 0
while (left + 1 < n && arr[left] <= arr[left + 1]) left++
// All are non-decreasing
if (left == n - 1) return 0
var right = n - 1
while (0 <= right - 1 && arr[right - 1] <= arr[right]) right--
var result = Int.MAX_VALUE
val originalRight = right
/**
0 1 2 3 4 5 6 7 8
1, 2, 3, 10, 4, 2, 3, 5
L R
Fix L, search the first R that satisfies arr[L] <= arr[R]
1, 2, 3, 10, 4, 2, 3, 5
L R
*/
while (right < n && arr[left] > arr[right]) right++
result = minOf(result, right - left - 1)
/**
0 1 2 3 4 5 6 7 8
1, 2, 3, 10, 4, 2, 3, 5
L R
Fix R, search the first L that satisfies arr[L] <= arr[R]
1, 2, 3, 10, 4, 2, 3, 5
L R
*/
right = originalRight
while (left >= 0 && arr[left] > arr[right]) left--
result = minOf(result, right - left - 1)
return if (result == Int.MAX_VALUE) 0 else result
}