Different O(n) solution with explaination


#1

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.

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

  2. Now everytime you come across a number x you convert number at x-1 into negative.

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

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

    }


#2

I am getting TLE for similar solution in python