# Python solution with detailed explanation

• 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
```.``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.