MissingInteger

Write a function:

    int solution(vector<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].

#include <unordered_map>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    unordered_map<int, int> map;
    
    for (int i = 0; i < int(A.size()); i++) {
        if (A[i] > 0) {
            map[A[i]] = i;    
        }
    }
    
    for (int i = 1; i < int(map.size() + 1); i++) {
        if (map.find(i) == map.end()) return i;     
    }
    
    return int(map.size() + 1);
}