Given an array of integers, write a method to find indices m and n such that if you sort elements from m through n, the entire array would be sorted.

package miscellaneous;

//Given an array of integers, write a method to find indices m and n such that if you
//sort elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence)

//What exactly need to do, lets understand with example.
//Examples:
//1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], 
//your program should be able to find that the subarray lies between the indexes 3 and 8.
//Array is partially sorted but the portion between the index 3 and 8 is unsorted and if that is sorted then complete array will be sorted. 

//2) If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], 
//your program should be able to find that the subarray lies between the indexes 2 and 5.
//Array is partially sorted but the portion between the index 2 and 5 is unsorted and if that is sorted then complete array will be sorted.

//How to achieve this.
//First how to find that array is sorted or not, traverse from i=0 to n and check if arr[i]<arr[i+1], if you don't found any mismatch then array is sorted.
//If you found any mismatch, then that is the index where mismatch starts.
//Now you have to find the end mismatch as well, that is uptill where this mismatch is present, for this starts from end and iterate until you find breaking decreasing order.
//Now you have 2 index, one is minIndex(index where mismatch started from left side), and one is maxIndex(index where mismatch started from right side),

//Now to find the unsorted subarray index, we need to find out minimum and maximum element present in the bunch between minIndex and maxIndex, 
//once the minimum element in bunch is known, now for this minimum element travel from left till one find the element greater than minimum found between bunch, that will be starting index of unsorted array.
//once the maximum element in bunch is known, now for this maximum element travel from right till one find the element smaller than maximum found between bunch, that will be ending index of unsorted array.
public class MinLenUnsortedSubarrayInSortedArray {
 public static void main(String[] args) {

  int arr[] = {10,20,30,40,50,45};
  findIndexOfUnsortedSubArray(arr);
 }

 private static void findIndexOfUnsortedSubArray(int arr[]){
  int leftIndex = findNonContinuityFromLeft(arr);
  if(leftIndex == -1){
   System.out.println("Arr is sorted");
   return;
  }
  int rightIndex = findNonContinuityFromRight(arr);  
  int minIndex=leftIndex, maxIndex=rightIndex;
  
  //findMinMaxBetweenLeftAndRightIndex
  int min = arr[minIndex];
  int max = arr[maxIndex];
  for (int i = minIndex; i <= maxIndex; i++) {
   if(arr[i]<min){
    min = arr[i];
   }
   if(arr[i]>max){
    max = arr[i];
   }
  }
  
  int startIndex = findMinBetween(arr, min, 0, minIndex);
  int endIndex = findMaxBetween(arr, max, arr.length-1, maxIndex);
  System.out.println(startIndex + " " + endIndex);
 }
 
 private static int findNonContinuityFromLeft(int arr[]){
  for (int i = 1; i < arr.length; i++) { 
   if(arr[i-1]>arr[i]){
    return i-1;
   }
  }
  return -1;
 }
 
 private static int findNonContinuityFromRight(int arr[]){
  for (int i = arr.length-1; i >= 0; i--) { 
   if(arr[i]<arr[i-1]){
    return i;
   }
  }
  return -1;
 }
 
 private static int findMinBetween(int arr[], int min, int start, int end){
  for (int i = start; i <= end; i++) {
   if(arr[i]>min){
    return i;
   }
  }
  return -1;
 }
 
 private static int findMaxBetween(int arr[], int max, int start, int end){
  for (int i = start; i >= end; i--) {
   if(arr[i]<max){
    return i;
   }
  }
  return -1;
 }
}