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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray to be Removed to Make Array Sorted

Difficulty: Medium

Problem 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.

Key Insights

  • The array needs to be transformed into a non-decreasing order by removing the shortest possible contiguous subarray.
  • The problem can be approached using two pointers to find the longest prefix and suffix of the array that are already sorted.
  • The idea is to determine the maximum length of the combined sorted prefix and suffix, and the minimum length of the subarray to remove can be calculated from this.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize two pointers to identify the longest non-decreasing prefix and suffix of the array. We will maintain a stack to help in identifying the valid segments of the array that can be left after removing the shortest subarray. By computing the lengths of these segments, we can determine the minimum length of the subarray that needs to be removed.

Code Solutions

def findLengthOfShortestSubarray(arr):
    n = len(arr)
    if n <= 1:
        return 0

    # Step 1: Find the longest non-decreasing prefix
    left = 0
    while left + 1 < n and arr[left] <= arr[left + 1]:
        left += 1

    # If the entire array is non-decreasing
    if left == n - 1:
        return 0

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

    # Step 3: Initialize the answer to remove the entire array
    answer = min(n - left - 1, right)

    # Step 4: Try to combine the prefix and suffix
    j = right
    for i in range(left + 1):
        # Move j to find a valid position
        while j < n and arr[i] > arr[j]:
            j += 1
        # Calculate the minimum length of subarray to remove
        answer = min(answer, j - i - 1)

    return answer
← Back to All Questions