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

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;
}

You can also try this code with Online Java Compiler

Run Code

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.

Check out this problem - Search In Rotated Sorted Array

You can use Coding Ninjas Studio 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!!!