Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Key Takeaways
Last Updated: Mar 27, 2024

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

Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


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.

Also read, Euclid GCD Algorithm

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:-



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



3 6



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

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job


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])
    //Check if the entire array is sorted
    if (S == n-1)
        System.out.println("The complete array is sorted");
        // Increment the 'a' pointer till n-1

        for(a = n - 1; a > 0; a--)
        if(A[a] < A[a-1])
    // 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;
        for( i = n -1; i >= a+1; i--)
        if(A[i] < maximum)
          a = i;
    System.out.println("We need to sort the subarray"+" ("+S+" "+a+")");


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.



  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!!!


Previous article
Creative Sorting problem
Next article
Maximum Gap
Live masterclass