<p>Given an unsorted integer array <code>nums</code>. Return the <em>smallest positive integer</em> that is <em>not present</em> in <code>nums</code>.</p>

<p>You must implement an algorithm that runs in <code>O(n)</code> time and uses <code>O(1)</code> auxiliary space.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,0]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The numbers in the range [1,2] are all in the array.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,4,-1,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 1 is in the array but 2 is missing.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,8,9,11,12]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The smallest positive integer 1 is missing.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        if (nums.size() <= 1) { if (nums[0] == 1) { return 2; } else { return 1; } }


        int index = get_first_positive_element(nums);
        std::cout << index << std::endl;
        if (index == -1 && nums.size()> 1) { return 1; }
        else if (index != -1 && nums.size() > 1) {
            std::vector<int> vec(nums.begin() + index, nums.end());
            if (vec.size() == 1) { if (vec[0] == 1) { return 2; } else { return 1; } }
            else if (has_one(vec)==0 && has_zero(vec) == 0 && vec.size() > 1) { return 1; }
            else if (has_zero(vec) == 1 && is_complete(vec) && vec.size() > 1) { return vec.back() + 1; }
            else if (has_one(vec) == 1 && is_complete(vec) && vec.size() > 1) { return vec.back() + 1; }
            else if ((has_zero(vec) == 1 || has_one(vec) == 1) && is_complete(vec) == 0 && vec.size() > 1) {
                return vec[Get_missing_Positive(vec)] + 1;
            }
            else { return -2; }
        }
        else { return -2; }
    }

    bool has_one(std::vector<int>&)const;
    bool has_zero(std::vector<int>&)const;
    int get_first_positive_element(std::vector<int>&)const;
    bool is_complete(std::vector<int>&)const;
    int Get_missing_Positive(std::vector<int>&) const;
};



bool Solution::has_one(std::vector<int>& nums)const {
    int i = 0;
    bool Bbool = 0;
    while (i < nums.size() - 1 && Bbool == 0) {
        if (nums[i] == 1) { Bbool = 1; }
        i++;
    }
    return Bbool;
}
bool Solution::has_zero(std::vector<int>& nums)const {
    int i = 0;
    bool Bbool = 0;
    while (i < nums.size() - 1 && Bbool == 0) {
        if (nums[i] == 0) { Bbool = 1; }
        i++;
    }
    return Bbool;
}

int Solution::get_first_positive_element(std::vector<int>& vect)const {
    int i = 0;
    while (vect[i] < 0 && i< vect.size() - 1) { i = i + 1; }
    std::cout << i << std::endl;
    if (i <= vect.size()-1) { return i; }
    else { return -1; }
}



bool Solution::is_complete(std::vector<int>& nums)const {
    int i = 0;
    bool Bbool = 1;
    while (i < nums.size()-1 && Bbool == 1) {
        i = i + 1;
        if (nums[i] - nums[i - 1] > 1) { Bbool = 0; }
    }
    return Bbool;
}

int Solution::Get_missing_Positive(std::vector<int>& nums) const {
    int i = 1;
    while (nums[i] - nums[i - 1] <= 1 && nums.size() >= 1) { i = i + 1; }
    return i-1;
}
37703