<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:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """
        We will use nums as a hashmap. I.e. nums[i - 1]
        will be True if the integer i is in the original
        nums array and False otherwise.
        """
        n = len(nums)
        # Set all invalid integers (<= 0 or greater than n)
        # to False. This means if type(nums[i]) == int it will
        # have to be a valid integer and if the type is a bool
        # we can ignore that index as it has become a hashmap key.
        for i, num in enumerate(nums):
            if num <= 0 or num > n:
                nums[i] = False
        # This recursive function will follow a path of valid
        # integer indices. This prevents us from overwriting an
        # index that contains a valid integer when making the 
        # hashmap.
        def recurse(i, num, status):
            """
            i: index of valid integer
            num: valid integer
            status: if no integer that we've seen points to this
            index, the hashmap value will be False for right now.
            If we are coming from a valid integer that points to this
            index, set the hashmap value to True.
            """
            nums[i] = status
            if type(nums[num - 1]) == bool:
                nums[num - 1] = True
            else:
                j = num - 1
                other_num = nums[j]
                nums[j] = True
                recurse(j, other_num, True)
            return
        # Loop through all members of the array:
        for i, num in enumerate(nums):
            if type(num) == int:
                recurse(i, num, False)
            # Do nothing if this index is already a hash key.
        # Now go and find the first key with a False value in
        # the hashmap.
        for i in range(n):
            if nums[i] is False:
                return i + 1
        # Else: every key has a True value. This n + 1 is the 
        # smallest positive integer not contained in the original
        # array.
        return n + 1

26506