Find the Minimum Length Unsorted Subarray, Sorting Which Makes the Complete Array Sorted

Soumya Agrawal
Last Updated: May 13, 2022

Introduction

 

Finding the minimum length unsorted subarray is grounded on the Sorting algorithm. We have to find the minimum length of unsorted subarray for which the complete array gets sorted.

What do you mean by subarray?

A subarray is a contiguous part of an array. For example arr=[1,2,3], the subarrays are (1),(2),(3),(1,2),(2,3),(1,2,3).

 

Now let’s understand the problem statement.

 

Problem Statement

We are given an Array. We need to find an unsorted subarray of minimum length such that if we sort that unsorted subarray, the complete array gets sorted. We need to output (s, e) where s is the starting index of the unsorted subarray and e is the ending index of the unsorted array.

 

Let us see a few examples:-

 

Input: 

arr: [1, 2, 3, 9, 7, 8, 6, 10]

 

Output: 

3 6

 

Explanation:

If we sort the subarray (3, 6), we will get the following array:-

[1, 2, 3, 6, 7, 8, 9, 10].

 

Approach

 

We will solve this question using the two pointers. We will be following the given steps:-

  1. We will initialize two pointers ‘s’ and ‘e.’ ‘s’ will equal 0, and e will be equal to N-1.
  2. We will keep incrementing the s pointer until we find the first index whose value is greater than the next index value.
  3. We will keep decrementing the ‘e’ pointer until we find the index whose value is smaller than the previous index value.
  4. Using the above two steps, we have found the subarray, which is not sorted at all.
  5. Now, we need to check if there are still a few elements that we need to include in our current subarray.
  6. For that, we will first find the minimum and the maximum elements of the unsorted subarray we found above.
  7. Now, we will find the first index from the subarray (0, s) whose value is greater than the minimum unsorted subarray and update ‘s’ to this index.
  8. Now, we will find the last index from the subarray (e, N-1) whose value is smaller than the maximum value of the unsorted array and update ‘e’ to this index.
  9. In the end, we will print (s, e).

 

Refer to the below implementation of the above approach.

static void minUnsorted(int A[], int n)
{
    int S = 0, a= n-1, i, maximum, minimum;  
  
    // Increment S
    for (S = 0; S < n-1; S++)
    {
        if (A[S] > A[S+1])
          break;
    }
  
    //Check if the entire array is sorted
    if (S == n-1)
    {
        System.out.println("The complete array is sorted");
        return;
    }
        // Increment the 'a' pointer till n-1

        for(a = n - 1; a > 0; a--)
    {
        if(A[a] < A[a-1])
          break;
    }
  
    // Find the minimum and maximum element of unsorted array
    maximum = A[S]; minimum = A[S];
    for(i = S + 1; i <= a; i++)
    {
        if(A[i] > maximum){
          maximum = A[i];
        }
        if(A[i] < minimum){
          minimum = A[i];
        }
    }
  
        for( i = 0; i < S; i++)
    {
        if(A[i] > minimum)
        {
          S = i;
          break;
        }    
    }
      
        for( i = n -1; i >= a+1; i--)
    {
        if(A[i] < maximum)
        {
          a = i;
          break;
        }
    }
      
    System.out.println("We need to sort the subarray"+" ("+S+" "+a+")");
    return;
}

 

Time Complexity: The time complexity of the above approach is O(N) because we are running the for loops of O(N) time complexity only.

 

Space Complexity: O(1) is the space complexity of this approach because we are not using any auxiliary space.

 

FAQs

  1. What is a subarray?
    It is a contiguous set of elements of an array that can be obtained if a few elements from the end and a few elements from the starting array are removed.
     
  2. What is the Time complexity of the approach used?
    O(N) is the time complexity of the above approach because we are running the for loops of O(N) time complexity only.

 

Key Takeaways

 

This blog has covered the following things related to minimizing a binary string by repeatedly removing even-length substrings of the same characters:

  1. We first discussed the approach to solve this question.
  2. Then we discussed the time and space complexity of the approach used to solve this question.

 

You can use CodeStudio for practice and gain knowledge about Array, then practice some questions requiring you to take your basic knowledge on Array a notch higher; you can visit our Guided Path for Array

 

Keep Coding!!!

 

Was this article helpful ?
0 upvotes