Find the smallest window in array sorting which will make the 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++ implementation –
 

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

Notify of
avatar
Sort by:   newest | oldest | most voted
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);

}

wpDiscuz