Description: Given an array ‘arr’ of ‘n’ elements, find the minimum length subarray, such that sorting this subarray makes the whole array sorted.

 
If video does not load, Click here
 
Example:
Input:

5   6   8   7   12  18  13  17  22 

Output:

8  7  12  18  13  17

Algorithm:

1.Start scanning the array from left to right and find the first element whose value is greater than the element to the right of it. Store it’s index in ‘p’.

2.Start scanning the array from right to left and find the first element whose value is less than the element to the left of it. Store it’s index in ‘q’.

3.Store the maximum and minimum value occuring between indexes ‘p’ and ‘q’(arr[p..q]) in ‘max’ and ‘min’ respectively.

4.Search for the first element in subarray arr[0..p-1]  which is greater than the ‘min’. If found, store the corresponding index in ‘p’.

5.Search for last element in subarray arr[q+1..n-1] which is smaller than ‘max’. If found, store corresponding index in ‘q’.

6.Subarray between indexes ‘p’ and ‘q’ is the minimum length unsorted array, which can be sorted to obtain a fully sorted array. 

Implementation using C:

/*The following function finds the required subarray.*/

void Unsortedsubarray(int arr[], int n)

{

  int p,q, i, max, min;  

  /*Step 1*/

  for (p= 0;p< n-1;p++)

  {

    if (arr[p] > arr[p+1])

      break;

  }

  if (p== n-1)

  {

    printf("Array is already sorted");

    return;

  }

  /*Step 2*/

  for(q= n - 1;q> 0;q--)

  {

    if(arr[q] < arr[q-1])

      break;

  }

  max = arr[p]; min = arr[p];

  /*Step 3*/

  /*Update 'max' and 'min' to store maximum and minimum values in arr[p..q]*/

  for(i = p + 1; i <= q; i++)

  {

    if(arr[i] > max)

      max = arr[i];

    if(arr[i] < min)

      min = arr[i];

  }

  /*Step 4*/

  for( i = 0; i <p; i++)

  {

    if(arr[i] > min)

    { 

      p = i;

      break;

    }     

  }

  /*Step 5*/

  for( i = n -1; i >= q+1; i--)

  {

    if(arr[i] < max)

    {

      q= i;

      break;

    }

  } 

  /*Step 6*/

  printf(" The unsorted subarray lying between %d-%d indices makes whole array sorted.", p, q);

  return;

}

Time Complexity:

O(n)

Go to top