Java perfect Solution .. Short and Simple Sol O(n) and O(1)


#1

public class Solution {
public int firstMissingPositive(ArrayList a) {
int n=a.size();
ArrayList b=new ArrayList<>();
if(n==1 && a.get(0)==1)
return 2;
if(n==1)
return 1;

    Iterator itr = a.iterator(); 
    while (itr.hasNext()) 
    { 
        int x = (Integer)itr.next(); 
        if (x < 0) 
            itr.remove(); 
    } 
    n=a.size();
  
    for (int i=0;i<n;i++)
    {
        int x=Math.abs(a.get(i));
        if(x<n)
        { 
            a.set(x,-Math.abs(a.get(x)));
        }
    }
      
    int i=0;
     for (i=1;i<n;i++)
    {
        if(a.get(i)>0)
        {
            return i;
        }
    }
    return n+1;
}

}


#2

It’ll be O(n^2) as a.set(index,value) for arrayList will take O(N) and you’re Using it in Loop that runs for n times so it’s O(n^2) time Comp.