Given an unsorted list find minimum window that if it is sorted then the whole list is sorted

This solution is inspired by suggestion by Li Peng: http://allenlipeng47.com/PersonalPage/index/list/1/nkey

All complicated problems can be solved by or starting by looking at simple case. The simple case of this problem is that the list is sorted. For the sorted list, we can observe the boundaries of the sublist are the minimum and maximum values of the sublist. If the boundaries are not qualified, we have to sort the window.

Again we start with a worse case of sliding window, and find a way to shrink the window to smallest as possible. And when we shrink this window, we need to keep track of the min or max found in the window so far. 

And remember the data structure of min stack and max stack, which we can keep track of min or max in LIFO order. In my implementation in stead of using stack, I used indexed array to present the stack and keep track of the min and max. 

static int[] findMinUnsortedWindow(int[] nums){

int len = nums.length;

if(len<2)

return new int[]{-1,-1};

//represent the min index of the sublist from i to len-1

int[] min = new int[len];

                //represent the max index of the sublist from 0 to i 

int[] max = new int[len];

max[0] = 0;

for(int i=1;i<len;i++){

if(nums[i]>=nums[max[i-1]])

max[i] = i;

else

max[i] = max[i-1];

}

min[len-1] = len-1;

for(int i=len-2;i>=0;i--){

if(nums[i]<=nums[min[i+1]])

min[i] = i;

else

min[i] = min[i+1];

}

//shrinking left boundaries

int left = 0;

while(left<len && left == min[left]){left++;}

//shrinking right boundaries

if(left==len)

return new int[]{-1, -1};

int right = len-1;

while(right>=0 && right == max[right]){right--;}

return new int[]{left, right};

}