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

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

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?