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

Question

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])

• 301_Moved_Permanently: So, if I understand the second exemple correctly, 0 is not a positive integer?
• 301_Moved_Permanently: And what about the other constraints? Can there be duplicated numbers in the array? What should [4, 5, 7, 8] return, 6 or 1?
• Grajdeanu Alex: @LinMa a full description of this challenge would really help. Could you please add a link / full description to your question ?
• Eugene Lisitsky: Not sure about O(n), for + while can give you O(n**2)
• ChatterOne: @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.

Answer 1

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

• Lin Ma: Love your comments, Alex. mark your reply as answer.

Answer 2

How about this solution:

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?

• hjpotter92: It is not using constant space.
• RandomDude: Since the space used directly depends on the data processed due to the dict?
• hjpotter92: Yes. Go through this post: stackoverflow.com/a/10844411/1190388 :)
• Pitto: Hei @RandomDude! Sorry but totally unrelated... I own a t-shirt with the face shown in your avatar... Who is this guy? :)