Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.
Examples:
- If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between indexes 3 and 8.
- If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], your program should be able to find that the subarray lies between indexes 2 and 5.
Approach 1:
- Find the candidate unsorted subarray
- Scan from left to right and find the first element which is greater than the next element. Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
- Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order). Let e be the index of such an element. In the above example 1, e is 7 (index of 31).
- Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
- Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
- Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element. There is no such element in above example 1.
- Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element. In the above example 1, e is changed to 8 (index of 35)
- Print s and e.
// C++ program to find the Minimum length Unsorted Subarray,
// sorting which makes the complete array sorted
C++:
#include<bits/stdc++.h>
usingnamespacestd;
voidprintUnsorted(intarr[], intn)
{
ints = 0, e = n-1, i, max, min;
// step 1(a) of above algo
for(s = 0; s < n-1; s++)
{
if(arr[s] > arr[s+1])
break;
}
if(s == n-1)
{
cout << "The complete array is sorted";
return;
}
// step 1(b) of above algo
for(e = n - 1; e > 0; e--)
{
if(arr[e] < arr[e-1])
break;
}
// step 2(a) of above algo
max = arr[s]; min = arr[s];
for(i = s + 1; i <= e; i++)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
// step 2(b) of above algo
for( i = 0; i < s; i++)
{
if(arr[i] > min)
{
s = i;
break;
}
}
// step 2(c) of above algo
for( i = n -1; i >= e+1; i--)
{
if(arr[i] < max)
{
e = i;
break;
}
}
// step 3 of above algo
cout << "The unsorted subarray which"
<< " makes the given array"<< endl
<< "sorted lies between the indices "
<< s << " and "<< e;
return;
}
intmain()
{
intarr[] = {10, 12, 20, 30, 25,
40, 32, 31, 35, 50, 60};
intarr_size = sizeof(arr)/sizeof(arr[0]);
printUnsorted(arr, arr_size);
getchar();
return0;
}
// This code is contributed
// by Akanksha Rai
Java:
importjava.io.*;
classMain
{
staticvoidprintUnsorted(intarr[], intn)
{
ints = 0, e = n-1, i, max, min;
// step 1(a) of above algo
for(s = 0; s < n-1; s++)
{
if(arr[s] > arr[s+1])
break;
}
if(s == n-1)
{
System.out.println("The complete array is sorted");
return;
}
// step 1(b) of above algo
for(e = n - 1; e > 0; e--)
{
if(arr[e] < arr[e-1])
break;
}
// step 2(a) of above algo
max = arr[s]; min = arr[s];
for(i = s + 1; i <= e; i++)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
// step 2(b) of above algo
for( i = 0; i < s; i++)
{
if(arr[i] > min)
{
s = i;
break;
}
}
// step 2(c) of above algo
for( i = n -1; i >= e+1; i--)
{
if(arr[i] < max)
{
e = i;
break;
}
}
// step 3 of above algo
System.out.println(" The unsorted subarray which"+
" makes the given array sorted lies"+
" between the indices "+s+" and "+e);
return;
}
publicstaticvoidmain(String args[])
{
intarr[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};
intarr_size = arr.length;
printUnsorted(arr, arr_size);
}
}
PHP:
<?php
// PHP program to find the Minimum length Unsorted Subarray,
// sorting which makes the complete array sorted
functionprintUnsorted(&$arr, $n)
{
$s= 0;
$e= $n- 1;
// step 1(a) of above algo
for($s= 0; $s< $n- 1; $s++)
{
if($arr[$s] > $arr[$s+ 1])
break;
}
if($s== $n- 1)
{
echo"The complete array is sorted";
return;
}
// step 1(b) of above algo
for($e= $n- 1; $e> 0; $e--)
{
if($arr[$e] < $arr[$e- 1])
break;
}
// step 2(a) of above algo
$max= $arr[$s];
$min= $arr[$s];
for($i= $s+ 1; $i<= $e; $i++)
{
if($arr[$i] > $max)
$max= $arr[$i];
if($arr[$i] < $min)
$min= $arr[$i];
}
// step 2(b) of above algo
for( $i= 0; $i< $s; $i++)
{
if($arr[$i] > $min)
{
$s= $i;
break;
}
}
// step 2(c) of above algo
for( $i= $n- 1; $i>= $e+ 1; $i--)
{
if($arr[$i] < $max)
{
$e= $i;
break;
}
}
// step 3 of above algo
echo" The unsorted subarray which makes ".
"the given array ". "\n".
" sorted lies between the indees ".
$s. " and ". $e;
return;
}
// Driver code
$arr= array(10, 12, 20, 30, 25, 40,
32, 31, 35, 50, 60);
$arr_size= sizeof($arr);
printUnsorted($arr, $arr_size);
// This code is contributed
// by ChitraNayal
?>
Output:
The unsorted subarray which makes the given array sorted lies between the indices 3 and 8
Time Complexity : O(n)
Auxiliary Space : O(1)
Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.
More: Why is it faster to process sorted array than an unsorted array ?