Question

Write a method that takes an array of integers as input. The method should find and display two indices m and n such that if you sort the elements from index m to index n the entire array would be sorted. The method should minimize m − n, that is it should find the smallest subsection for the array that needs to be sorted. For example,

int[] a = {2, 4, 6, 7, 9, 8, 12, 15, 5, 13, 18, 20}

get_unsorted_section(a); // prints 2 and 9

Please use Java. Thanks!

Answer 1

class Main 
{ 
        static void get_unsorted_section(int arr[], int n) 
        { 
        int s = 0, e = n-1, i, max, min; 
        for (s = 0; s < n-1; s++) 
        { 
                if (arr[s] > arr[s+1]) 
                break; 
        } 
        if (s == n-1) 
        { 
                return; 
        } 
                
        for(e = n - 1; e > 0; e--) 
        { 
                if(arr[e] < arr[e-1]) 
                break; 
        } 
                
        max = arr[s]; min = arr[s]; 
        for(i = s + 1; i <= e; i++) 
        { 
                if(arr[i] > max) 
                max = arr[i]; 
                if(arr[i] < min) 
                min = arr[i]; 
        } 
                
        for( i = 0; i < s; i++) 
        { 
                if(arr[i] > min) 
                { 
                s = i; 
                break; 
                }        
        } 
                
        for( i = n -1; i >= e+1; i--) 
        { 
                if(arr[i] < max) 
                { 
                e = i; 
                break; 
                } 
        } 
                        
        System.out.println(s+" "+e); 
        return; 
        } 
                
        public static void main(String args[]) 
        { 
        int arr[] = {2, 4, 6, 7, 9, 8, 12, 15, 5, 13, 18, 20}; 
        int arr_size = arr.length; 
        get_unsorted_section(arr, arr_size); 
        } 
} 

Here is the desire code. Please check it out. I hope it helps.
Thank you