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

**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 –

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<climits> using namespace std; // Function to find the smallest window in the array sorting which will // make the entire array sorted void findSubarray(int arr[], int n) { int leftIndex = -1, rightIndex = -1; // traverse from left to right and keep track of maximum so far int max_so_far = INT_MIN; for (int i = 0; i < n; i++) { if (max_so_far < arr[i]) max_so_far = arr[i]; // find the last position that is less than the maximum so far if (arr[i] < max_so_far) rightIndex = i; } // traverse from right to left and keep track of minimum so far int min_so_far = INT_MAX; for (int i = n - 1; i >= 0; i--) { if (min_so_far > arr[i]) min_so_far = arr[i]; // find the last position that is more than the minimum so far if (arr[i] > min_so_far) leftIndex = i; } cout << "Sort array from index " << leftIndex << " to " << rightIndex; } // main function int main() { int arr[] = { 1, 3, 2, 7, 5, 6, 4, 8 }; int n = sizeof(arr)/sizeof(arr[0]); findSubarray(arr, n); return 0; } |

`Output:`

Sort array from index 1 to 6

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Util { // Function to find the smallest window in the array sorting // which will make the entire array sorted public static void findSubarray(int[] A) { int leftIndex = -1, rightIndex = -1; // traverse from left to right and keep track of maximum so far int max_so_far = Integer.MIN_VALUE; for (int i = 0; i < A.length; i++) { if (max_so_far < A[i]) { max_so_far = A[i]; } // find the last position that is less than the maximum so far if (A[i] < max_so_far) { rightIndex = i; } } // traverse from right to left and keep track of minimum so far int min_so_far = Integer.MAX_VALUE; for (int i = A.length - 1; i >= 0; i--) { if (min_so_far > A[i]) { min_so_far = A[i]; } // find the last position that is more than the minimum so far if (A[i] > min_so_far) { leftIndex = i; } } System.out.print("Sort array from index " + leftIndex + " to " + rightIndex); } // main function public static void main(String[] args) { int[] A = { 1, 3, 2, 7, 5, 6, 4, 8 }; findSubarray(A); } } |

`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 our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

The minimum is 1 not 3 pls explain…

Also do your algorithm for this example

10 11 12 7 6 5 1 4 8

Thanks for sharing your concerns. Could you please elaborate as we don’t see any problem with the solution. It looks like you have misunderstood the problem statement.

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);

}

}

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);

}