The idea behind the question is that the smallest missing positive number cannot be more than A.size(). So the answer has to be between 1 to N.

convert all the negatives into n+1, now all your numbers are positive

Now everytime you come across a number x you convert number at x1 into negative.

you check and make sure the number is not negative already, as this may cause double negative.

now the first index that is positive is the smallest positive number that is absent.
public class Solution { public int firstMissingPositive(ArrayList<Integer> A) { int n = A.size(); // first get negatives out of you way for(int i=0;i<A.size();i++) { if(A.get(i) < 0) { A.set(i,n+1); } } // convert all encountered indices to negative for(int i=0;i<n;i++){ int num = Math.abs(A.get(i)); if(num > n  num == 0) continue; int pos = num1; if(A.get(pos)>0) A.set(pos,A.get(pos)); // "if" avoids double negative } for(int i=0;i<n;i++) { if(A.get(i) > 0) return i+1; } return n+1; }
}