Java O(n) simple solution with comments


#1

The idea is till the subarray of the input array is sorted (minimum element so far array from left to right) will be equal to the input array, same for (max element so far array from right to left), we only need to look at first fluctuations.
public class Solution {
public ArrayList subUnsort(ArrayList A) {
int L, R,size;
L = R = -1;
size = A.size();
ArrayList result = new ArrayList();

    int[] minArr = new int[size];  // min array containing minimum element so far from right to left
    int[] maxArr = new int[size]; // max array containing maximum element so far from left to right
    
    maxArr[0] = A.get(0);
    minArr[size-1] = A.get(size-1);
    
    int i = 1;
    int j = size-2;
    
    while( i < size && j >= 0){
        maxArr[i] = Math.max(maxArr[i-1],A.get(i));
        minArr[j] = Math.min(minArr[j+1],A.get(j));
        i++;
        j--;
    }
    // Checking for the fluctuations between the input array and minArr
    int k = 0; 
    for(k = 0; k< size; k++){
        if(A.get(k) != minArr[k]){
            L = k;
            break;
        }
    }
    // for a sorted array input the minArr and maxArr will be equal to the sorted array input
    if(k == size){
        result.add(-1);
        return result;
    }
    
    // Checking for the fluctuations between the input array and minArr
    for( k = size-1; k >= 0; k--){
        if(A.get(k) != maxArr[k]){
            R = k;
            break;
        }
        
    }
    result.add(L);
    result.add(R);
    return result;
}
}