Min subarray (or sublist) to sort to make an unsorted array (or list) sorted

Give a list of unsorted number, find the min window or min sublist or min subarray of the input, such as if sublist is sorted, the whole list is sorted too.

For example, given array a={1,2,3,5,4,4,3,3,7,8,9} then min subarray to sort the complete array sorted is {5,4,3,3}. More example : for a={1,2,3,5,6,4,2,3,3,7,8,9} then min subarray is {2,3,5,6,4,2,3,3}, for a={1,2,3,5,6,4,3,3,7,8,9,2} then min subarray is {2,3,5,6,4,2,3,3,7,8,9,2} etc.

Apparently the problems looks very complicated. But if we look into an example then we will see that it is rather one of simpler problems. Just believe in your intuition!

For example, a={1,2,3,5,4,4,3,3,7,8,9}. Note that 4 comes after 5 breaking the ascending sorting order. We understand the 5 and 4 must be contained in the resultant min subarray. Now believe in your intuition. How did you figure out that 5,4,3,3 is the answer? Because our brain affixed our attention to the two numbers : 5 and the right most 3. this is because these two numbers are related. How? Because 5 tells us the first number to be included in the min list. This also tells us that the left of 5 , i.e. 3 is the minimum number that may appear in the min list(why?).

We identified the start of the min list. But where does it end? As we know that 3 may be the minimum that ma appear in the list. This means the min list should contain all number greater than equal to 3 starting from 5. So, if we can identify somehow the max number that may appear in this min list then the minList ends at the position which has a higher value than the max number (why?).

What is the maximum number that can appear in the list? As we know 3 is the min then we can identify the right most 3 and get the maximum among elements between the left boundary i.e. 5 and rightmost min i.e. rightmost 3. The maximum tells us where is the rightmost boundary of the min array. The right boundary is the first number greater than the max on the right of the right most min. For example, in the current example it is 7. Then all numbers from 5 until 7 (excluding 7) constitute the resulting min subarray.

Below is the implementation of the above idea. The algorithm runs in O(n) time and O(1) space.

//O(n) time algorithm
public static List<Integer> minListToBeSorted(int[] nums){
	//find the first index from left to right where the sorted order disrupted
	//i.e. first index where next element is smaller 
	int minIndex = -1;
	for(int i = 1; i< nums.length; i++){
		if(nums[i] < nums[i-1]){
			minIndex = i;
			break;
		}
	}
	
	//So, we got a potential mid element of the unsorted list
	//the minimum list must have a minimum element which is smaller or equal to this element
	for(int i = minIndex; i<nums.length; i++){
		if(nums[i] < nums[minIndex]){
			minIndex = i;
		}
	}
	
	//we can use the min element to identify the left boundary of the list because the left boundary
	//is the first element to the left greater than equal to this smallest element.
	//at the same time we can compute the maximum element in the left of this min element
	int l = minIndex;
	int r = minIndex;
	int maxLeft = nums[l];
	while(l >= 0 && nums[l] >= nums[minIndex]){
		maxLeft = Math.max(maxLeft, nums[l]);
		l--;
	}
	
	//we can use the max element to find the right most boundary of the min unsorted list by finding
	//first node in right of the smallest element that is greater than the max element
	while(r < nums.length && nums[r] <= maxLeft){
		r++;
	}
	
	//all elments between 
	List<Integer> res = new  ArrayList<Integer>();
	for(int i = l+1; l>=0 && r<=nums.length && i<r; i++){
		res.add(nums[i]);
	}
	return res;
}