The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

Write a function:

    int solution(int A[]);

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−1,000,000..1,000,000].

Note:

One of the given arrays above is:

    [1, 3, 6, 4, 1, 2]

If this array is sorted, it would be:

    [1, 1, 2, 3, 4, 6]

It can clearly be seen that the missing positive integer greater than 0 is 5. If 5 were included, then the missing integer would be 7 = 6+1, according to the above criteria.

After a possible sort, if there are negative integers, then the search has to begin from 1, excluding 0.

The lesson for this problem is Counting Elements. Counting elements is also a form of sorting. This should give the candidate the idea, that a count array should be used, and the missing integer, searched from count index 1, which is just after count index 0. The missing integer (count index), should have a value (number of occurrences) of 0.

If the missing integer is not found, then the missing integer should be taken as the maximum number in the array A, plus 1; according to the above criteria.

Illustration with given Example Data

When the given array, A is

then the count array is:

The number of occurrences of the value 5 in A is 0 in the count array. 5 is the missing integer in A.

When the given array, A is:

then the count array is:

Remember that the indexes of the count array are the values of the given array. There may be a convenience 0, which is not found in the given array, as in this case. There is no index (above 0) with number of occurrences of 0 in this case (the convenience 0 index is not considered).

The indexes to consider in the count array, are in the range, 1 to 3 (inclusive). The maximum integer in A is 3. According to the above criteria, the answer has to be 4 = 3 + 1. In the count array, 4 could have been the next index after the highest index of 3. Then, 1 is added to the last count index.

When the given array, A is [−1, −3], the smallest positive integer is taken (considered) as +1, because all the elements in A are negative. If the count array is to be produced from this given array, based on possible positive integers (values) in the given array, then the count array will be:

where the index of 0 here is the convenience 0. So the answer is 0 + 1, according to the above criteria.

Since there is no index from 1 upwards, in the count array, with 0 as number of occurrences, then there is supposedly no missing smallest positive integer in A, in the range, 1 to infinity (inclusive). 1 could have been the next index after the highest index of 0 here, in the count array. So the answer is taken (considered) as 1 = 0 + 1; according to the above criteria.

The number of elements (length of given array) in the given array, [−1, −3] is 2. The algorithm takes approximately 2 = N operations to scan array, A to produce the count array (of 1 element). The algorithm then takes 1 operation to "read" through the count array.

The number of operations here, is O(2+1), better written as O(N+1), and officially quoted as O(N). Remember that in this case, all the values (integers) in A are negative.

The Code

The algorithm scans the given array, A to produce the count array. After that it "reads" through the count array, looking for any index from 1 to m (inclusive) that has 0 as number of occurrence. m is the maximum number in the given array A. The first index found, beginning from the left of the count array, is the missing smallest positive integer. If no such index is found, then the answer is m+1. Negative elements in the given array A, are ignored. The code is as follows (read through it and the comments):

#include <stdio.h>

int solution(int A[], int N) {
    int count[N+1];    //N is M here
    for (int i=0; i < N+1; i++)
        count[i] = 0;    //initializing count array
    
    for (int i=0; i < N; i++){
        if ( A[i] <= N && A[i] >= 0) {  //considering only elements in A, from 0 to m (inclusive)
            count[A[i]] += 1;   
        }
    }
    
    for (int i=1; i <= N; i++){  //missing integer is less than m
        if (count[i]==0)
            return i;
    }

    return N+1;  //if A consists of elements from 1 to m
}
  
int main(int argc, char **argv) 
{
    int A1[] = {1, 3, 6, 4, 1, 2};
    int N1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int ret1 = solution(A1, N1);
    printf("%i\n", ret1);
    
    int A2[] = {1, 2, 3};
    int N2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int ret2 = solution(A2, N2);
    printf("%i\n", ret2);
    
    int A3[] = {-1, -3};
    int N3 = sizeof(A3) / sizeof(A3[0]);    //length of given array
    int ret3 = solution(A3, N3);
    printf("%i\n", ret3);
    
    int A4[] = {2};
    int N4 = sizeof(A4) / sizeof(A4[0]);    //length of given array
    int ret4 = solution(A4, N4);
    printf("%i\n", ret4);
    
    return 0; 
}

The output is:

    5
    4
    1
    1

The very last return statement, "return N+1;" will be executed, if all the numbers in A are from 1 to m (inclusive). If the missing smallest positive integer is within the range, 1 to m (inclusive), then the previous return statement, "return i;" will return the index from the count array. There are only two return statements in the solution() function above.

In the third for-loop in the given function, the condition, "i <= N" accounts for "m+1".

The time complexity for the called function is O(N+M), with N for scanning the given array to produce the content of the count array, and M for scanning the count array to check if any element (value) is 0. The O(M) time to create the count array, initializing everything (element) to zero, is ignored here. The space complexity is O(N+M), for the two arrays.

When the given array is {-1, -3}, the count array remains at the initialized state of:

The index 1 has the value 0, and so 1 is returned as the smallest positive missing integer, according to the above criteria.

Thanks for reading.