//find smallest sub-array which when sorted makes the entire giver array sorted
//Time Complexity O(n) | Space Compelxity O(1)
import java.util.*;
class A
{
	public static void main(String[] args) 
	{
		int[] arr = new int[]{1,2,4,7,10,11,7,12,6,7,16,18,19};
		int[] index = subArraySort(arr); //index[0] left index of subarray index[1] right index of subarray
		System.out.println("left and right index of min subarray to be sorted is");
		System.out.println(Arrays.toString(index));
		System.out.println("left index "+index[0]);
		System.out.println("right index is "+index[1]);
		
	}
	public static int[] subArraySort(int[] arr)
	{
		//to store the left and right index of subarray to be sorted
		int[] subarray = new int[2];
		//subarray[0] -> left index of subarray
		//subarray[1] -> right index of subarray

		//To keep track of minimu and maximum of all elemnts that are out of order
		int minOutOfOrder = Integer.MAX_VALUE;
		int maxOutOfOrder = Integer.MIN_VALUE;

        //for all elemnts in array firs determine which all are outOfOrder
        //and among them find minOutOfOrder and maxOutOfOrder
		for(int i = 0 ; i < arr.length ; i++)
		{
			if(isOutOfOrder(i,arr[i],arr)) //true = out of order ,false = not out of order
			{
				minOutOfOrder = Math.min(minOutOfOrder,arr[i]);
				maxOutOfOrder = Math.max(maxOutOfOrder,arr[i]);
			}
		}
		//System.out.println(minOutOfOrder);
		//System.out.println(maxOutOfOrder);
		int left = 0;
		int right = arr.length-1;
        
        //find the correct postion of both in the array
        //and that will be the subarray to be sorted
		while(minOutOfOrder>=arr[left])
		{
          left++;
		}
		while(maxOutOfOrder<=arr[right])
		{
			right--;
		}
		return new int[]{left,right};
	}
	public static boolean isOutOfOrder(int idx , int num , int[] arr)
	{
		//if it is the first element check if it is greater than the 2nd element 
		//if true -> it is out of order
		if( idx== 0)
		{
			return num > arr[idx+1];
		}
		//if it is the last element in the array check if it is smaller than the 2nd last element in the array
		//if truw -> it is out of order
		if(idx==arr.length-1)
		{
			return num < arr[idx-1];
		}
		//for intermediate elements check for either of
		//the current number is lesser than the previous number
		//0r
		//the current number is greater than the next number
		//if either of the condition is true->return true -> the element is out of order

		 return num > arr[idx+1] | num < arr[idx-1];
	}
}