Missing integer variation - O(n) solution needed

By pigeonhole principle, at least one of the numbers 1, 2, ..., n+1 is not in the array. Let us create a boolean array b of size n+1 to store whether each of these numbers is present.

Now, we process the input array. If we find a number from 1 to n+1, we mark the corresponding entry in b. If the number we see does not fit into these bounds, just discard it and proceed to the next one. Both cases are O(1) per input entry, total O(n).

After we are done processing the input, we can find the first non-marked entry in our boolean array b trivially in O(n).

Simple solution 100% in Java.

Please note it is O(nlogn) solution but gives 100% result in codility.

public static int solution(final int[] A) 
{   
   Arrays.sort(A);
   int min = 1;

   // Starting from 1 (min), compare all elements, if it does not match 
   // that would the missing number.
   for (int i : A) {
     if (i == min) {
       min++;
     }
   }

   return min;
}

wrote this today and got 100/100. not the most elegant solution, but easy to understand -

public int solution(int[] A) {
    int max = A.length;
    int threshold = 1;
    boolean[] bitmap = new boolean[max + 1];

    //populate bitmap and also find highest positive int in input list.
    for (int i = 0; i < A.length; i++) {
        if (A[i] > 0 && A[i] <= max) {
            bitmap[A[i]] = true;
        }

        if (A[i] > threshold) {
            threshold = A[i];
        }
    }

    //find the first positive number in bitmap that is false.
    for (int i = 1; i < bitmap.length; i++) {
        if (!bitmap[i]) {
            return i;
        }
    }

    //this is to handle the case when input array is not missing any element.
    return (threshold+1);
}