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
    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;
}

}