<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>


        # constraints: O(1) extra space, O(n) time

        # brute: starting from 1 and incrementing each time u see that number
        #   would need to make multiple passes until num doesnt change, worst case n^2

        # improved: sort the array, either first elem if not 1, or first elem that doesnt incr by 1
        #   nlogn
        
        # ------ I THINK THIS JUST ENDS UP BEING A N^2 SCAN LIKE BEFORE BUT WAY UGLIER
        # thought: 2 pointers, cur = 1

        #   [5, 6, 3, 1, 2, 7]
        #   5, 7 | 1 -> move pointers inwards from larger elem first
        #   5, 2 | 1
        #   6, 2 | 1
        #   3, 2 | 1
        #   1, 2 | 3 -> match = move from that pointer, but how to know when to move outwards?
        #   3, 2 | 4
        #   3, 7 | 4
        #   6, 7 | 4
        #   5, 7 | 4
        # rules
        #   - move the matching pointer in/outwards, else move the larger elem; match increments answer
        #       - if larger elem is on a boundary for that IN/OUT direction, move the other pointer
        #   - if pointers touch or return to boundaries:
        #       - if match that iteration, reverse IN/OUT direction and continue
        #       - else return answer
        # end state = (pointers touching OR pointers back at boundaries) AND cur did not change that iter
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        #[3, 4, -1, 1]
        #[None, 4, None, None]
        def set_target(target):
            if target is not None and target >= 0 and target < len(nums):
                new_target = nums[target]
                nums[target] = None
                if new_target:
                    set_target(new_target - 1)

        for i in range(len(nums)):
            if nums[i]: # skip 0 and None
                set_target(nums[i] - 1)

        for i, x in enumerate(nums):
            if x != None:
                return i + 1
        return len(nums) + 1
29878