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 x-1 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 = num-1; 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; }}