Leetcode: First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

We could use a boolean array of length n in order to indicate whether the element is present or not, but instead of creating this array we are going to use the input array to mark it we use the sign for this. Hence we have to remove all the negative or zero values before. 

public class Solution {

    public int firstMissingPositive(int[] A) {

        int length = A.length;

        int i=0;

        while(i<length)

        {

            if(A[i]<=0)

                swap(A,i,--length);

            else

                i++;

        }

        for(i=0; i<length; i++)

        {

            if(Math.abs(A[i])<=length)

                A[Math.abs(A[i])-1]=-Math.abs(A[Math.abs(A[i])-1]);

        }

        for(i=0; i<length; i++)

        {

            if(A[i]>0)

                return i+1;

        }

        return length+1;

    }

    

    private void swap(int[] A, int pos1, int pos2)

    {

        int temp=A[pos1];

        A[pos1]=A[pos2];

        A[pos2]=temp;

    }

}