We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray to be Removed to Make Array Sorted

Number: 1679

Difficulty: Medium

Paid? No

Companies: DE Shaw, razorpay, Meta, Google, Amazon

Problem Description

Given an integer array, remove a contiguous subarray (which can be empty) such that the remaining array is non-decreasing. The goal is to determine the minimum length of the subarray that must be removed.

Key Insights

  • A non-decreasing array has the property that every element is less than or equal to its next element.
  • You can identify a longest non-decreasing prefix from the beginning and a longest non-decreasing suffix from the end.
  • The main challenge is to find the optimal "connection" point between the prefix and suffix, ensuring that the last element of the prefix is not greater than the first element of the suffix.
  • Consider edge cases where the array is already sorted or completely unsorted, ensuring one keeps the minimal removal.

Space and Time Complexity

Time Complexity: O(n) — We traverse the array a few times using two pointers. Space Complexity: O(1) — We use only a constant amount of extra space.

Solution

The solution strategy works as follows:

  1. Identify the longest non-decreasing prefix from the start.
  2. Identify the longest non-decreasing suffix from the end.
  3. The simplest answers might be to remove either the suffix or the prefix entirely.
  4. Then, use a two-pointer approach, where you iterate through the prefix and for each element, find a position in the suffix such that the suffix element is >= the current prefix element.
  5. The minimum removal length is then the gap between these corresponding indices.
  6. This strategy ensures we only remove the smallest necessary subarray to join the prefix and suffix while keeping the order.

Code Solutions

# Python Solution

def findLengthOfShortestSubarray(arr):
    n = len(arr)
    
    # Find the longest non-decreasing prefix
    left = 0
    while left + 1 < n and arr[left] <= arr[left + 1]:
        left += 1

    # If the whole array is already non-decreasing, no removal is needed
    if left == n - 1:
        return 0

    # Find the longest non-decreasing suffix
    right = n - 1
    while right - 1 >= 0 and arr[right - 1] <= arr[right]:
        right -= 1

    # Initialize answer with removing either prefix or suffix completely
    res = min(n - left - 1, right)  # Remove from left+1 to end or from beginning to right-1

    # Use two pointers to merge prefix and suffix
    i, j = 0, right
    while i <= left and j < n:
        # if the element from prefix is less than or equal to element from suffix
        if arr[i] <= arr[j]:
            # update result with minimum subarray removal length
            res = min(res, j - i - 1)
            i += 1
        else:
            # move right pointer to try and find a valid suffix element
            j += 1

    return res

# Example usage:
example1 = [1,2,3,10,4,2,3,5]
print(findLengthOfShortestSubarray(example1))  # Output should be 3
← Back to All Questions