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

Min subarray (or sublist) to sort to make an unsorted array (or list) sorted - Algorithms and Problem SolvingAlgorithms and Problem Solving

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}.

//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;
}

Read full article from Min subarray (or sublist) to sort to make an unsorted array (or list) sorted - Algorithms and Problem SolvingAlgorithms and Problem Solving