**Solution with discussion** https://discuss.leetcode.com/topic/76042/python-solution-with-detailed-explanation

**First Missing Positive** https://leetcode.com/problems/first-missing-positive/

**Solution using extra space: O(N) time and space**

- If the length of the nums array is N, then the first missing positive will be between 1 to N+1. Think Why N+1? We can have in the array 1 to N.
- Take an temp array of size N and for any number x in nums such that 1<=x<=N, mark temp[x-1]. Then simply walk the temp array and report the first unmarked index.

```
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp, N = [None]*len(nums), len(nums)
for x in nums:
if 1<=x<=N:
temp[x-1] = x
for i in range(N):
if temp[i] == None:
return i+1
return N+1
```

**Optimized solution with O(1) Space**

- Simply traverse the nums array and put any number within [1, N] in their right place. For example if 2 is in that input, then put 2 at index 1.
- Now traverse this "shuffled" array again. You expect 1 at 0th index. Otherwise it is missing. Then you expect 2 at 1st index and so on.
- Above idea can be a little tricky. What about cases like [1] and [1,1] - i.e. 1 is in its place or there are duplicates - we need to advance pointer regardless.

```
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
N, i = len(nums), 0
while i < N:
while 1<=nums[i]<=N:
idx_expected = nums[i]-1
if nums[i] == nums[idx_expected]:
break
nums[i], nums[idx_expected] = nums[idx_expected], nums[i]
i = i + 1
for i in range(N):
if nums[i] != i+1:
return i+1
return N+1
```.
```