3
\$\begingroup\$

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

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Love your comments, Alex. mark your reply as answer. \$\endgroup\$ – Lin Ma Dec 12 '16 at 3:48
1
\$\begingroup\$

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?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It is not using constant space. \$\endgroup\$ – hjpotter92 Jul 22 '18 at 9:26
  • \$\begingroup\$ Since the space used directly depends on the data processed due to the dict? \$\endgroup\$ – RandomDude Jul 22 '18 at 9:32
  • 1
    \$\begingroup\$ Yes. Go through this post: stackoverflow.com/a/10844411/1190388 :) \$\endgroup\$ – hjpotter92 Jul 22 '18 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.