# Given an unsorted integer array, find the first missing positive integer

Here is the problem, any advice about code improvement, more efficient implementation in terms of time complexity, functional bugs, etc. are appreciated.

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and use constant space.

def firstMissingPositive(nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 1
for i,v in enumerate(nums):
if v > len(nums):
nums[i]=-1
elif v <= 0:
nums[i]=-1
else:
while i+1 != nums[i] and 0<nums[i]<=len(nums):
#print i, nums[i]-1, nums[i], nums[nums[i]-1]
v = nums[i]
nums[i] = nums[v-1]
nums[v-1] = v
#nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
if nums[i] > len(nums) or nums[i] <=0:
nums[i] = -1
for i,v in enumerate(nums):
if nums[i] != i+1:
return i+1
return len(nums)+1

if __name__ == "__main__":
print firstMissingPositive([1,2,0])
print firstMissingPositive([3,4,-1,1])

• So, if I understand the second exemple correctly, 0 is not a positive integer? Commented Dec 8, 2016 at 7:43
• And what about the other constraints? Can there be duplicated numbers in the array? What should [4, 5, 7, 8] return, 6 or 1? Commented Dec 8, 2016 at 8:21
• @LinMa a full description of this challenge would really help. Could you please add a link / full description to your question ? Commented Dec 8, 2016 at 9:20
• Not sure about O(n), for + while can give you O(n**2) Commented Dec 8, 2016 at 11:15
• @Alex I see your point. I think you're considering only the swaps, but maybe you should consider (also) the comparisons. In the worst case you'll still do one swap, but n comparisons for each n-1 in the list. Commented Dec 8, 2016 at 15:33

PEP8

Python uses underscore as naming separator in function and variable names, see PEP8

Naming

for i,v in enumerate(nums)


It's better to use some obvious names so instead of i,v you should use index, value

Improvements

You've got a right idea on how to solve this, but there are some minor things in your implementation that can be improved.

for i,v in enumerate(nums):
if v > len(nums):
nums[i]=-1
elif v <= 0:
nums[i]=-1
else:


this part can be simplified to

if  0 >= value > len(nums):
continue


Now your while loop can make infinite number of cycles on such list [3,4,3,-1] so you need to handle this, also you don't have to replace items that are <= 0 or items that are >= len(nums) with -1 you can just skip them.

So in the end your code should look like this:

def first_missing_positive(nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 1
for index, value in enumerate(nums):
if len(nums) < value <= 0:
continue
while index + 1 != nums[index] and 0 < nums[index] <= len(nums):
v = nums[index]
nums[index], nums[v-1] = nums[v-1], nums[index]
nums[v-1] = v

# Don't create infinite loops
if nums[index] == nums[v-1]:
break

for index, value in enumerate(nums, 1):
if value != index:
return index
return len(nums) + 1


def first_missing_positive(nums):
cnt = {}
for x in nums:
cnt[x] = 1

fnd = 1
for i in range(len(nums)):
if cnt.get(fnd, 0) == 0:
return fnd
fnd += 1
return fnd


According to timeit on my local machine it is a bit faster than the solution from Alex. Is it breaking the "O(n) time and use constant space" requirement?

• It is not using constant space. Commented Jul 22, 2018 at 9:26
• Since the space used directly depends on the data processed due to the dict? Commented Jul 22, 2018 at 9:32
• Yes. Go through this post: stackoverflow.com/a/10844411/1190388 :) Commented Jul 22, 2018 at 9:42
• Hei @RandomDude! Sorry but totally unrelated... I own a t-shirt with the face shown in your avatar... Who is this guy? :) Commented Jun 17, 2021 at 12:36