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? – 301_Moved_Permanently Dec 8 '16 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? – 301_Moved_Permanently Dec 8 '16 at 8:21
• @LinMa a full description of this challenge would really help. Could you please add a link / full description to your question ? – Grajdeanu Alex Dec 8 '16 at 9:20
• Not sure about O(n), for + while can give you O(n**2) – Eugene Lisitsky Dec 8 '16 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. – ChatterOne Dec 8 '16 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. – hjpotter92 Jul 22 '18 at 9:26
• Since the space used directly depends on the data processed due to the dict? – RandomDude Jul 22 '18 at 9:32
• Yes. Go through this post: stackoverflow.com/a/10844411/1190388 :) – hjpotter92 Jul 22 '18 at 9:42