-3
\$\begingroup\$

This is a Leetcode problem:

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

Note:

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

Here is my first solution to this problem:

class Solution:

    def __init__(self, A):
         self.A = A

    def firstMissingPositive(self, A):
        #Get rid of non-positive elements
        for n in A:
            if n <= 0:
                A.remove(n)
        if A == []:
            return 1

        maximum = max(A)
        res = [0] * maximum

        for n in A:
            if n > 0:
                res[n - 1] = 1

        for i in range(len(res)):
            if res[i] == 0:
                return i + 1
        return maximum + 1

A = #Enter a list.

missing_integer = Solution(A)
print(missing_integer.firstMissingPositive(A))

Here are the inputs/outputs for my program. They have the same outputs as the examples given in the challenge here:

A = [1,2,0]
>>> 3

A = [3,4,-1,1]
>>> 2

A = [7,8,9,11,12]
>>> 1

Here is my second solution to this problem:

# O(n) time

def firstMissingPositive(nums):

    for i in range(len(nums)):
        while 0 <= nums[i] - 1 < len(nums) and nums[nums[i]-1] != nums[i]:
            tmp = nums[i] - 1
            nums[i], nums[tmp] = nums[tmp], nums[i]
    for i in range(len(nums)):
        if nums[i] != i + 1:
            return i + 1
    return len(nums) + 1

nums = #Enter a list.
print(firstMissingPositive(nums))

Inputs/outputs - Same as above.

So, I would like to have a code review for the efficiency of both the solutions.

Any help would be highly appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ @perennial_noob You're just misunderstanding the problem. The smallest positive number "missing" from the array doesn't refer to a gap in the array itself, but the first positive integer that's not included in the array. I made the same interpretation as you at first, but the third examples clarifies this. \$\endgroup\$ – Sedsarq May 27 at 6:57
2
\$\begingroup\$

Only the second solution meets the memory requirement of using constant extra space. The first solution has other issues as well, for example some unnecessary optimization attempts such as removing negative values, which is likely to do more harm than good, because removing items from the middle of a list is usually a costly operation.

The second solution can be slightly improved by replacing the classic range loops with for index, value in enumerate(nums) loops. I would also add a blank line between two loops, for slightly better readability.

\$\endgroup\$
1
\$\begingroup\$

EDIT: While accepted by the site, this solution doesn't meet the memory requirement.

This looks like an opportunity to use a set. By keeping the numbers in a set instead of a list, you can look up successive values of n directly, no element-by-element searching required. So, make a set, put n at 1, then see how far you can increase n before it's no longer contained in the set:

def firstMissingPositive(nums):
    n = 1
    s = set(nums)
    while n in s:
        n += 1
    return n
\$\endgroup\$
  • 4
    \$\begingroup\$ You can't use sets in this task. Look at the requirement: *Your algorithm should run in O(n) time and uses constant extra space.* set(nums) is not constant space, it can use up to N space. \$\endgroup\$ – vurmux May 23 at 14:30
  • 1
    \$\begingroup\$ Ah, I suppose that's true @vurmux . The site accepted it though, I guess the rules aren't enforced. \$\endgroup\$ – Sedsarq May 23 at 14:33
  • 1
    \$\begingroup\$ I suppose there is just bad tests for this task. Sometimes on these sites one can use incorrect algorithms (according to requirements) and they are accepted by the test system. \$\endgroup\$ – vurmux May 23 at 14:35
1
\$\begingroup\$

The best solution here is a modified counting sort. If we store the first integer not yet found, we can move an element of value i to the ith spot of the array until we find a duplicate or something bigger than the array size, at which point we throw that away and go to the next index. At the end of this process, we will have an array where the first i elements of the array have the value i.

\$\endgroup\$

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.