# Java solution for O(N) and O(NlogN)

#1

public class Solution {
public ArrayList subUnsort(ArrayList A) {

``````    //O(N) solution
int max  = -1;
int start =Integer.MAX_VALUE;
int end =-1;
ArrayList<Integer> ans = new ArrayList<>();
for(int i = 0; i<A.size(); ++i)
{
if(A.get(i)>=max)
{
max = A.get(i);
}
else
{
//the rightmost wrong element which we have gor so far
end = i;
//store the min element which is to not in the right place and
//needs to be replaced.
start = Math.min(start, A.get(i));
}

}

//if we did not fing any wrong placed element
else
{//just look for the place where we can put our lowest wrong placed element,
//and thus that would be the left index for sorting

int j =0;
while(A.get(j)<=start){
++j;
}
// add the j(the left most element tat we just computed)
// the end was the right most wrong placed element that we already calculated.
}
return ans;

//O(NlogN) solution
// just sort the array and then compare the first and the last unmatching element.
// ArrayList<Integer> temp = new ArrayList<>();
// ArrayList<Integer> ans = new ArrayList<>();
// Collections.sort(A);
// int st =-1;
// for(int k =0; k<A.size(); ++k)
// {
//     if(A.get(k)!= temp.get(k))
//     {
//         st = k;
//         break;
//     }

// }
// if(st==-1)
// {
// }
// else
// {   int en =-1;
//     for(int k =A.size()-1; k>-1; --k)
//     {
//         if(A.get(k)!= temp.get(k))
//         {
//             en = k;
//             break;
//         }

//     }
// }
// return ans;
}
``````

}