<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:
        # Step 1
        # Leave only positive
        i = 0
        j = len(nums) - 1
        while i <= j:
            if nums[i] < 1 and nums[j] > 0:
                c = nums[i]
                nums[i] = nums[j]
                nums[j] = c
                i += 1
                j -= 1
            elif nums[i] >= 1:
                i += 1
            elif nums[j] < 1:
                j -= 1

        # All positive numbers are now at the bottom of the list
        # the length is i
        positiveLen = i

        print(nums, positiveLen)

        # Step 2
        # Remove numbers > positiveLen
        for k in range(positiveLen):
            if nums[k] > positiveLen:
                nums[k] = 0

        print(nums)

        # Step 3
        # Rearrange numbers
        for k in range(positiveLen):
            newIndex = nums[k] % (positiveLen + 1)
            if newIndex == 0:
                continue
            newIndex -= 1
            nums[newIndex] += nums[k] * (positiveLen + 1)
            #print(k, nums)

        print(nums)

        # Step 4
        # Find first zero
        for k in range(positiveLen):
            if nums[k] <= positiveLen:
                return k + 1

        return positiveLen + 1
            
32363