#1574

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Shortest Subarray to be Removed to Make Array Sorted

Find the shortest subarray to remove in order to make an array non-decreasing using binary search and two-pointer techniques.

array two pointers binary search stack monotonic stack

Problem Statement

Given an integer array, your goal is to remove a subarray such that the remaining elements in the array form a non-decreasing sequence. The length of the shortest subarray to remove must be returned. A subarray is defined as a contiguous subsequence of the array.

The challenge requires handling arrays of varying sizes efficiently. For large arrays, an optimal solution is necessary, so leveraging techniques such as binary search and two pointers becomes crucial. The key is finding the longest non-decreasing subarray from either the start or the end and minimizing the length of the subarray to be removed.

Examples

Example 1

Input: arr = [1,2,3,10,4,2,3,5]

Output: 3

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

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

The array is already non-decreasing. We do not need to remove any elements.

Constraints

1 <= arr.length <= 105
0 <= arr[i] <= 109

Solution Approach

Binary Search for Valid Answer

Use binary search to efficiently identify the shortest removable subarray. By narrowing down the search space, this approach allows you to find the smallest subarray that can be removed while ensuring the remaining elements are non-decreasing.

Two Pointers for Non-Decreasing Subarrays

Apply two pointers to identify the longest non-decreasing subarrays starting from the beginning and end of the array. This helps you isolate the portion of the array that needs to be removed, reducing unnecessary checks and optimizing the solution.

Monotonic Stack for Efficiency

A monotonic stack can be utilized to track the indices of elements as you traverse the array. By maintaining this stack, you can efficiently determine when to remove the subarray and minimize the computational complexity.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity of the optimal solution is O(N), where N is the length of the array, due to the use of binary search and two-pointer techniques. Space complexity is O(1), as only a few variables are used to store intermediate values and results.

What Interviewers Usually Probe

Strong candidates will demonstrate proficiency with binary search and two-pointer techniques.
Look for the ability to identify the key patterns in array manipulation and optimally apply them.
Candidates should be able to explain how binary search can be used to reduce the search space effectively.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by overlooking binary search, leading to unnecessary brute-force approaches.
Not recognizing the importance of non-decreasing subarrays from the beginning or end of the array.
Overcomplicating the problem with unnecessary data structures or inefficient algorithms.

Follow-up variants

Modify the problem by allowing multiple subarrays to be removed.
Introduce additional constraints, such as the array being sorted in descending order.
Extend the problem to handle cases where the array contains negative numbers.

FAQ

What is the key technique to solve the Shortest Subarray to be Removed to Make Array Sorted problem?

The key technique is binary search over the valid answer space, paired with two pointers to identify the longest non-decreasing subsequences.

How do I optimize the solution for large arrays in this problem?

Using binary search and two pointers helps optimize the solution, achieving a time complexity of O(N) while keeping space complexity to O(1).

What is the role of the monotonic stack in solving this problem?

The monotonic stack helps efficiently track the indices of the non-decreasing subarrays, making it easier to determine which subarray to remove.

Can the Shortest Subarray to be Removed to Make Array Sorted problem have multiple correct answers?

Yes, there can be multiple valid subarrays to remove, but the goal is to find the shortest one.

What is the time complexity of the optimal solution for this problem?

The time complexity is O(N), where N is the length of the array, due to the use of binary search and two-pointer techniques.

terminal

Solution

Solution 1: Two Pointers + Binary Search

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Solution 2: Two Pointers

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#1793 maximum score of a good subarray #962 maximum width ramp #2454 next greater element iv