Finding the first missing positive integer

Input: [8, -5, 0, 1, 4, 3]
Output: 2

Input: [4, 3, 1, 5, 2]
Output: 6

Input: [-3, -6, 0, 2, 5, 6]
Output: 1

One simple algorithm is to sort the given array and we can easily find out the missing number since the numbers will be in order. Sorting the array takes O(n log n) time and scanning the array takes O(n) time. So, over-all time complexity of this approach would be O(n log n). The code for the same is as follows.

private static int firstMissingPositive(int []arr) {
        if(null == arr)
            return -1;
        if(arr.length == 0)
            return 1;
        Arrays.sort(arr);
        int i;
        for(i = 0; i < arr.length && arr[i] < 1; i++){}

        int num = 1;
        while(i < arr.length && arr[i] == num) {
            num++;
            i++;
        }
        return num;
    }

We can optimize the above approach to run in O(n) time by taking O(n) extra space. This is a two step algorithm.

1. We can copy the positive numbers to another array say positives
2. Use the array elements to indicate to see which elements are present. We will negate the value at arr[v-1] if v is present.

Here is the code method to return first missing positive number given a list of non-negative numbers along with test cases.

/**
     * Given an array of non-negative numbers, return the first missing positive number
     * @param arr: array of non-negative numbers
     * @return First positive missing number
     */
    private static int firstMissingPositiveNum(int []arr) {
        //Assuming that we need to return -1 if array is null;
        //We can also chose to ignore this return and let it throw NullPointerException
        if(null == arr) {
            return -1;
        }
        if(arr.length == 0) {
            return 1;
        }

        int i;
        for(i = 0; i < arr.length; i++) {
            int val = Math.abs(arr[i]);
            //Check if we can represent this value in the array within the index range
            //negate the array element at index (val-1)
            if(val != 0 && val <= arr.length) {
               if(arr[val-1] > 0) {
                   arr[val-1] = -arr[val-1];
               }
            }
        }

        for(i = 0; i < arr.length; i++) {
            if(arr[i] > 0) {
                break;
            }
        }
        return i+1;
    }
    private static void testFirstMissingPositiveNum() {
        System.out.println(firstMissingPositiveNumber(new int[]{3})); //Expected output: 1
        System.out.println(firstMissingPositiveNumber(new int[]{})); //Expected output: 1
        System.out.println(firstMissingPositiveNumber(new int[]{4, 1, 2, 6, 5})); //Expected output: 3
        System.out.println(firstMissingPositiveNumber(new int[]{1, 2, 3, 4, 5, 7})); //Expected output: 6
        System.out.println(firstMissingPositiveNumber(new int[]{7, 5, 4, 3, 2, 1})); //Expected output: 6
        System.out.println(firstMissingPositiveNumber(new int[]{9, 2, 8, 1, 3, 6, 5, 7, 4})); //Expected output: 10
    }

This can further be optimized to run in O(n) time and O(1)extra space.

The idea is to re-arrange the array so that all negative elements first and positive elements next. This can be done in O(n) time.

Then use the second part of the array to find out the missing positive numbers. Following is the code for the same.

private static int firstMissingPositiveNumber(int []arr) {
        int positiveIndex = groupPositiveNegative(arr);
        if(positiveIndex < 0) { //null
            return -1;
        }
        if(positiveIndex == arr.length) // arr contains all negatives
            return 1;
        int positiveCount = arr.length - positiveIndex; //count of positive numbers
        //Make use of the positive element group of the array for keeping track of the positive numbers.
        //So we are going to modify the array
        //mark arr[positiveIndex] as negative if 1 is present
        //mark arr[positiveIndex + 1] as negative if 2 is present and so on...
        //mark arr[positiveIndex+ v - 1] as negative v is present in the array
        int i;
        for(i = positiveIndex; i < arr.length; i++) {
            int val = Math.abs(arr[i]);
            if(val <= positiveCount) {
                if(arr[val + positiveIndex - 1] > 0) {
                    arr[val + positiveIndex - 1] = -arr[val + positiveIndex - 1];
                }
            }
        }
        //Finally check for the elements which are not marked negative;
        //At the end of the loop, i+1 would be missing positive number,
        //since the array boundary started at positiveIndex, we need to add it.
        for(i = positiveIndex; i < arr.length; i++) {
            if(arr[i] > 0) {
                break;
            }
        }
        return i - positiveIndex + 1;
    }
private static int groupPositiveNegative(int []arr) {
        if(null == arr) {
            return -1;
        }
        if(arr.length == 0) {
            return 0;
        }
        int i, j;
        for(i = 0, j = arr.length; i < j; ) {
            while( i < arr.length && arr[i] <= 0) {
                i++;
            }

            while(j > 0 && arr[j-1] > 0) {
                j--;
            }
            if(i < j) {
                int temp = arr[i];
                arr[i] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        return j;
    }