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:
- 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].
- If arr[j] >= arr[i], try to update the answer using j – i – 1 and increment i to tighten the window.
- If arr[j] < arr[i], elements cannot be deleted in between, so increment j to loosen the window.
- 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:
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
