Length of smallest subarray to be removed such that the remaining array is sorted

0 0 6 minutes read

Given an array arr[] consisting of N integers, the task is to print the length of the smallest subarray to be removed from arr[] such that the remaining array is sorted.

Examples:

Input: arr[] = {1, 2, 3, 10, 4, 2, 3, 5}
Output: 3
Explanation:
The smallest subarray to be remove is {10, 4, 2} of length 3. The remaining array is {1, 2, 3, 3, 5} which are sorted.
Another correct solution is to remove the subarray [3, 10, 4].

Input: arr[] = {5, 4, 3, 2, 1}
Output: 4
Explanation:
Since the array is strictly decreasing, only a single element need to be kept in the array.
Therefore, required answer is 4.

Approach: The problem can be solved based on the following three ways to remove a subarray:

Remove the subarray from the left i.e left suffix.

Remove the subarray from the right ie, prefix.

Remove the subarray from the middle and merge the left and right part of the array.

Iterate over the arr[] from left to right, find the first index left that arr[left] > arr[left + 1]. So the subarray length to be removed to make the array sorted is N-left-1.
If left == N – 1, this array is already sorted, so return 0.
Iterate over the arr[] from right to left, find the first index right that arr[right] < arr[right – 1]. So the subarray length to be removed to make the array sorted is right.
Now initialize a variable mincount and take the minimum of N-left-1 and right.
Now calculate the minimum length of subarray to be removed from the middle of the array as well:
1. Let i = 0, j = right. And examine if elements in between, i and j (exclusive) can be deleted by comparing arr[i] and arr[j].
2. If arr[j] >= arr[i], try to update the answer using j – i – 1 and increment i to tighten the window.
3. If arr[j] < arr[i], elements cannot be deleted in between, so increment j to loosen the window.
4. Traverse the loop until i > left or j == N. And update the answer.
Return the mincount.

Below is the implementation of the above approach:

C++

// C++ program for the above approach  
#include<bits/stdc++.h> 
using namespace std; 
  
// Find the length of the shortest subarray  
int findLengthOfShortestSubarray(int arr[], int N) 
{ 
      
    // To store the result  
    int minlength = INT_MAX;  
  
    int left = 0; 
    int right = N - 1; 
  
    // Calculate the possible length of  
    // the sorted subarray from left  
    while (left < right &&  
       arr[left + 1] >= arr[left]) 
    { 
        left++; 
    } 
  
    // Array is sorted  
    if (left == N - 1)  
        return 0; 
  
    // Calculate the possible length of  
    // the sorted subarray from left  
    while (right > left &&  
       arr[right - 1] <= arr[right]) 
    { 
        right--; 
    } 
  
    // Update the result  
    minlength = min(N - left - 1, right);  
  
    // Calculate the possible length  
    // in the middle we can delete  
    // and update the result  
    int j = right;  
    for(int i = 0; i < left + 1; i++) 
    { 
        if (arr[i] <= arr[j]) 
        { 
              
            // Update the result  
            minlength = min(minlength, j - i - 1);  
        } 
        else if (j < N - 1) 
        { 
            j++; 
        } 
        else
        { 
            break; 
        } 
    } 
  
    // Return the result  
    return minlength;  
} 
  
// Driver Code 
int main() 
{ 
    int arr[] = { 6, 3, 10, 11, 15, 
                  20, 13, 3, 18, 12 }; 
    int N = sizeof(arr) / sizeof(arr[0]); 
      
    // Function call  
    cout << (findLengthOfShortestSubarray(arr, N)); 
} 
  
// This code is contributed by divyeshrabadiya07

Java

// Java program for the  
// above approach 
import java.util.*; 
class GFG { 
  
// Find the length of the shortest subarray 
static int findLengthOfShortestSubarray(int arr[], 
                                        int N) 
{ 
  // To store the result 
  int minlength = Integer.MAX_VALUE; 
  
  int left = 0; 
  int right = N - 1; 
  
  // Calculate the possible length of 
  // the sorted subarray from left 
  while (left < right &&  
         arr[left + 1] >= arr[left])  
  { 
    left++; 
  } 
  
  // Array is sorted 
  if (left == N - 1) 
    return 0; 
  
  // Calculate the possible length of 
  // the sorted subarray from left 
  while (right > left &&  
         arr[right - 1] <= arr[right])  
  { 
    right--; 
  } 
  
  // Update the result 
  minlength = Math.min(N - left - 1,  
                       right); 
  
  // Calculate the possible length 
  // in the middle we can delete 
  // and update the result 
  int j = right; 
    
  for (int i = 0; i < left + 1; i++)  
  { 
    if (arr[i] <= arr[j])  
    { 
      // Update the result 
      minlength = Math.min(minlength, 
                           j - i - 1); 
    } 
    else if (j < N - 1)  
    { 
      j++; 
    } 
    else 
    { 
      break; 
    } 
  } 
  
  // Return the result 
  return minlength; 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
  int arr[] = {6, 3, 10, 11, 15,  
               20, 13, 3, 18, 12}; 
  int N = arr.length; 
  
  // Function call 
  System.out.print( 
         (findLengthOfShortestSubarray(arr, N))); 
} 
} 
  
// This code is contributed by Chitranayal

Python3

# Python3 program for the above approach 
import sys 
  
# Find the length of the shortest subarray 
def findLengthOfShortestSubarray(arr): 
  
    # To store the result 
    minlength = sys.maxsize 
  
    left = 0
    right = len(arr) - 1
  
    # Calculate the possible length of 
    # the sorted subarray from left 
    while left < right and arr[left + 1] >= arr[left]: 
        left += 1
  
    # Array is sorted 
    if left == len(arr) - 1: 
        return 0
  
    # Calculate the possible length of 
    # the sorted subarray from left 
    while right > left and arr[right-1] <= arr[right]: 
        right -= 1
  
    # Update the result 
    minlength = min(len(arr) - left - 1, right) 
  
    # Calculate the possible length 
    # in the middle we can delete 
    # and update the result 
    j = right 
    for i in range(left + 1): 
  
        if arr[i] <= arr[j]: 
  
            # Update the result 
            minlength = min(minlength, j - i - 1) 
  
        elif j < len(arr) - 1: 
  
            j += 1
  
        else: 
  
            break
  
    # Return the result 
    return minlength 
  
  
# Driver Code 
arr = [6, 3, 10, 11, 15, 20, 13, 3, 18, 12] 
  
# Function Call 
print(findLengthOfShortestSubarray(arr)) 

C#

// C# program for the  
// above approach 
using System; 
  
class GFG { 
  
// Find the length of the shortest subarray 
static int findLengthOfShortestSubarray(int []arr, 
                                        int N) 
{ 
    
  // To store the result 
  int minlength = int.MaxValue; 
  
  int left = 0; 
  int right = N - 1; 
  
  // Calculate the possible length of 
  // the sorted subarray from left 
  while (left < right &&  
         arr[left + 1] >= arr[left])  
  { 
    left++; 
  } 
  
  // Array is sorted 
  if (left == N - 1) 
    return 0; 
  
  // Calculate the possible length of 
  // the sorted subarray from left 
  while (right > left &&  
         arr[right - 1] <= arr[right])  
  { 
    right--; 
  } 
  
  // Update the result 
  minlength = Math.Min(N - left - 1,  
                       right); 
  
  // Calculate the possible length 
  // in the middle we can delete 
  // and update the result 
  int j = right; 
    
  for(int i = 0; i < left + 1; i++)  
  { 
    if (arr[i] <= arr[j])  
    { 
        
      // Update the result 
      minlength = Math.Min(minlength, 
                           j - i - 1); 
    } 
    else if (j < N - 1)  
    { 
      j++; 
    } 
    else 
    { 
      break; 
    } 
  } 
  
  // Return the result 
  return minlength; 
} 
  
// Driver Code 
public static void Main(String[] args) 
{ 
  int []arr = { 6, 3, 10, 11, 15,  
                20, 13, 3, 18, 12 }; 
  int N = arr.Length; 
  
  // Function call 
  Console.Write(findLengthOfShortestSubarray( 
                 arr, N)); 
} 
} 
  
// This code is contributed by Amit Katiyar

Javascript

<script> 
  
// Javascript program for the above approach  
  
// Find the length of the shortest subarray 
function findLengthOfShortestSubarray(arr, N) 
{ 
      
    // To store the result 
    let minlength = Number.MAX_VALUE; 
      
    let left = 0; 
    let right = N - 1; 
      
    // Calculate the possible length of 
    // the sorted subarray from left 
    while (left < right && 
           arr[left + 1] >= arr[left]) 
    { 
        left++; 
    } 
      
    // Array is sorted 
    if (left == N - 1) 
        return 0; 
      
    // Calculate the possible length of 
    // the sorted subarray from left 
    while (right > left && 
           arr[right - 1] <= arr[right]) 
    { 
        right--; 
    } 
      
    // Update the result 
    minlength = Math.min(N - left - 1, 
                         right); 
      
    // Calculate the possible length 
    // in the middle we can delete 
    // and update the result 
    let j = right; 
      
    for(let i = 0; i < left + 1; i++) 
    { 
        if (arr[i] <= arr[j]) 
        { 
              
            // Update the result 
            minlength = Math.min(minlength, 
                                 j - i - 1); 
        } 
        else if (j < N - 1) 
        { 
            j++; 
        } 
        else
        { 
            break; 
        } 
    } 
      
    // Return the result 
    return minlength; 
} 
  
// Driver Code 
let arr = [  6, 3, 10, 11, 15, 
            20, 13, 3, 18, 12]; 
let N = arr.length; 
  
// Function call 
document.write( 
    (findLengthOfShortestSubarray(arr, N))); 
      
// This code is contributed by souravghosh0416 
  
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!