O(1) space can usually be done by mutating input list.

The idea is try moving elements within the array such that number `n`

is at index `n-1`

. Then loop from `0->len(input)-1`

, if `input[i] is None`

then `i + 1`

is missing. Otherwise return `len(input) + 1`

Few points to note:

- if
`n-1`

is out of array boundary, we can't find a new index to move to, just skip. - If
`n`

is already in its correct position`n - 1`

, do nothing.

```
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
tmp, nums[i] = nums[i], None
while tmp is not None and 0 <= tmp-1 < len(nums) and tmp != nums[tmp-1]:
nums[tmp-1], tmp = tmp, nums[tmp-1]
for i in range(len(nums)):
if nums[i] is None:
return i+1
return len(nums) + 1
```