 # 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 = 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){
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;
}

}