Find smallest window in array sorting which will make entire array sorted

Given an array of integers, find the smallest window in array sorting which will make the entire array sorted in increasing order.

 

For example,


Input:  { 1, 2, 3, 7, 5, 6, 4, 8 }
Output: Sort the array from index 3 to 6
 

Input:  { 1, 3, 2, 7, 5, 6, 4, 8 }
Output: Sort the array from index 1 to 6

 
We can easily solve this problem in linear time. Below is the complete algorithm –

1. Traverse array from left to right keeping track of maximum so far and note the last encountered index j which is less than the maximum so far.

2. Traverse array from right to left keeping track of minimum so far and note the last encountered index i which is more than the minimum so far.

3. Finally we sort the array from index i to j

 
For example, consider below array

   { 1, 2, 3, 7, 5, 6, 4, 8 }

If we traverse the array from left to right, the last encountered index which is less than the maximum so far is 6. Similarly, if we traverse the array from right to left, the last encountered index which is more than the minimum so far is 3. So, we need to sort the array from index 3 to 6.

C++

Download   Run Code

Output:

Sort array from index 1 to 6

Java

Download   Run Code

Output:

Sort array from index 1 to 6

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Tarun Mitra
Guest
Tarun Mitra

Single Traversal:
public static void main (String[] args) {
int[] arr = {1,3,2,7,4,5,6,8};
int startindex = -1;
int end = -1;
for(int i=0;i arr[i+1]){
if(startindex == -1)
startindex = i;
int temp = arr[i++];
while(i < arr.length && arr[i] < temp)
i++;
end = –i;
}
}
if(startindex != -1){
System.out.println("Sort array index from "+startindex+" to "+end);
}
}

Appun
Guest
Appun

I think we can solve the problem with just one traversal, check following code

public static void findSubarray (int [] input){
int n = input.length;
int leftIndex = -1;
int rightIndex = -1;
int runningLefIndex = -1;

int maxSoFar = Integer.MIN_VALUE;

for (int i = 0; i maxSofar){
maxSoFar = input[i];
runningLeftIndex = i;
}else{
rightIndex = i;
leftIndex = runningLeftIndex;
}
}

System.out.printLn(“we need to sort from “+leftIndex+” to “+rightUndex);

}