1574. Shortest Subarray to be Removed to Make Array Sorted

Description

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Constraints:

1 <= arr.length <= 10⁵
0 <= arr[i] <= 10⁹

Solutions

Solution 1: Two Pointers + Binary Search

Thinking

Delete one contiguous subarray so the rest is nondecreasing, and minimize the deletion. \(n\le 10^5\) forbids trying every interval. What remains is a prefix plus a suffix whose join is still sorted.

Find the longest nondecreasing prefix \([0,i]\) and suffix \([j,n)\). If they already cover the array the answer is \(0\); otherwise we may drop the whole suffix or the whole prefix. For each prefix end \(l\), binary-search the first suffix index \(r\) with \(arr[r]\ge arr[l]\), delete \((l,r)\), and keep the shortest.

First, we find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as \(\textit{nums}[0..i]\) and \(\textit{nums}[j..n-1]\), respectively.

If \(i \geq j\), it means the array is already non-decreasing, so we return \(0\).

Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is \(\min(n - i - 1, j)\).

Next, we enumerate the right endpoint \(l\) of the left prefix. For each \(l\), we can use binary search to find the first position greater than or equal to \(\textit{nums}[l]\) in \(\textit{nums}[j..n-1]\), denoted as \(r\). At this point, we can delete \(\textit{nums}[l+1..r-1]\) and update the answer \(\textit{ans} = \min(\textit{ans}, r - l - 1)\). Continue enumerating \(l\) to get the final answer.

The time complexity is \(O(n \times \log n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

Python3JavaC++Go

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i + 1 < n and arr[i] <= arr[i + 1]:
            i += 1
        while j - 1 >= 0 and arr[j - 1] <= arr[j]:
            j -= 1
        if i >= j:
            return 0
        ans = min(n - i - 1, j)
        for l in range(i + 1):
            r = bisect_left(arr, arr[l], lo=j)
            ans = min(ans, r - l - 1)
        return ans

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = Math.min(n - i - 1, j);
        for (int l = 0; l <= i; ++l) {
            int r = search(arr, arr[l], j);
            ans = Math.min(ans, r - l - 1);
        }
        return ans;
    }

    private int search(int[] arr, int x, int left) {
        int right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = min(n - 1 - i, j);
        for (int l = 0; l <= i; ++l) {
            int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin();
            ans = min(ans, r - l - 1);
        }
        return ans;
    }
};

func findLengthOfShortestSubarray(arr []int) int {
    n := len(arr)
    i, j := 0, n-1
    for i+1 < n && arr[i] <= arr[i+1] {
        i++
    }
    for j-1 >= 0 && arr[j-1] <= arr[j] {
        j--
    }
    if i >= j {
        return 0
    }
    ans := min(n-i-1, j)
    for l := 0; l <= i; l++ {
        r := j + sort.SearchInts(arr[j:], arr[l])
        ans = min(ans, r-l-1)
    }
    return ans
}

Solution 2: Two Pointers

Thinking

Solution 1 binary-searches each \(l\) and pays an extra \(\log n\). Both sides are sorted, so \(r\) only moves right as \(l\) grows. A monotone right pointer makes the second loop linear.

Similar to Solution 1, we first find the longest non-decreasing prefix and the longest non-decreasing suffix of the array, denoted as \(\textit{nums}[0..i]\) and \(\textit{nums}[j..n-1]\), respectively.

If \(i \geq j\), it means the array is already non-decreasing, so we return \(0\).

Otherwise, we can choose to delete the right suffix or the left prefix. Therefore, initially, the answer is \(\min(n - i - 1, j)\).

Next, we enumerate the right endpoint \(l\) of the left prefix. For each \(l\), we directly use two pointers to find the first position greater than or equal to \(\textit{nums}[l]\) in \(\textit{nums}[j..n-1]\), denoted as \(r\). At this point, we can delete \(\textit{nums}[l+1..r-1]\) and update the answer \(\textit{ans} = \min(\textit{ans}, r - l - 1)\). Continue enumerating \(l\) to get the final answer.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i + 1 < n and arr[i] <= arr[i + 1]:
            i += 1
        while j - 1 >= 0 and arr[j - 1] <= arr[j]:
            j -= 1
        if i >= j:
            return 0
        ans = min(n - i - 1, j)
        r = j
        for l in range(i + 1):
            while r < n and arr[r] < arr[l]:
                r += 1
            ans = min(ans, r - l - 1)
        return ans

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = Math.min(n - i - 1, j);
        for (int l = 0, r = j; l <= i; ++l) {
            while (r < n && arr[r] < arr[l]) {
                ++r;
            }
            ans = Math.min(ans, r - l - 1);
        }
        return ans;
    }
}

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = min(n - 1 - i, j);
        for (int l = 0, r = j; l <= i; ++l) {
            while (r < n && arr[r] < arr[l]) {
                ++r;
            }
            ans = min(ans, r - l - 1);
        }
        return ans;
    }
};

func findLengthOfShortestSubarray(arr []int) int {
    n := len(arr)
    i, j := 0, n-1
    for i+1 < n && arr[i] <= arr[i+1] {
        i++
    }
    for j-1 >= 0 && arr[j-1] <= arr[j] {
        j--
    }
    if i >= j {
        return 0
    }
    ans := min(n-i-1, j)
    r := j
    for l := 0; l <= i; l++ {
        for r < n && arr[r] < arr[l] {
            r += 1
        }
        ans = min(ans, r-l-1)
    }
    return ans
}

function findLengthOfShortestSubarray(arr: number[]): number {
    let [l, r, n] = [0, arr.length - 1, arr.length];

    while (r && arr[r - 1] <= arr[r]) r--;
    if (r === 0) return 0;

    let ans = r;
    while (l < r && (!l || arr[l - 1] <= arr[l])) {
        while (r < n && arr[l] > arr[r]) r++;
        ans = Math.min(ans, r - l - 1);
        l++;
    }

    return ans;
}

function findLengthOfShortestSubarray(arr) {
    let [l, r, n] = [0, arr.length - 1, arr.length];

    while (r && arr[r - 1] <= arr[r]) r--;
    if (r === 0) return 0;

    let ans = r;
    while (l < r && (!l || arr[l - 1] <= arr[l])) {
        while (r < n && arr[l] > arr[r]) r++;
        ans = Math.min(ans, r - l - 1);
        l++;
    }

    return ans;
}

1574. Shortest Subarray to be Removed to Make Array Sorted

Description

Solutions

Solution 1: Two Pointers + Binary Search

Solution 2: Two Pointers

Comments