Missing Integer

Return the minimal positive integer (greater than 0) that does not occur in A. For example, given:

A[0] = 1; A[1] = 3; A[2] = 6; A[3] = 4; A[4] = 1; A[5] = 2;

the function should return 5.

This is required to be in O(N) time complexity, with N from 0 to 100,000. Each element in A is from -2,147,483,647 to 2,147,483,647. These are the most extreme values that can be stored from a standard int in C/C++. Any more (or less) and the int will overflow.

Solution

If you read the PDF it describes using arrays as a means to count the frequency of numbers in a collection, in that the array indices represent the array values and the array elements are their frequency. However you should be safe guarding your program against the limits specified by codility, and by attempting to make an array or a vector of size N = 2,147,483,647 (which is defined in C as the macro INT_MAX) visual studio will refuse (I do not know about codility at present). Note you would need two of these, one for positives, one for negatives, or one twice as long for both.

I therefore used an associative array (std::map) to store the numbers and their frequencies, and return the first number with a zero frequency. It only stores the numbers that you encounter, and can store positives and negatives.

Note that the minimum positive number is always 1, so it is this number that you should always begin your search for when scanning the map. It will be the default answer if all input numbers are negative, or if the input numbers do not include a 1 (regardless of how many gaps may be in the numbers in A).