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
if(end == -1) ans.add(-1);
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.
ans.add(j);
ans.add(end);
}
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<>();
// temp.addAll(A);
// 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)
// {
// ans.add(-1);
// }
// else
// { int en =-1;
// for(int k =A.size()-1; k>-1; --k)
// {
// if(A.get(k)!= temp.get(k))
// {
// en = k;
// break;
// }
// }
// ans.add(st);
// ans.add(en);
// }
// return ans;
}
}