Leetcode 41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/

Because the problem requires O(n) time, so sorting is not applicable. Also constant space is required, so the hash mapping is not applicable, too.

The normal thought is to put all the positive numbers to their supposed positions. But what if the number is large? If we put it in the back, what should we do about the swapped number? We should just stay and check it again. So it is very important to confirm that those two swapped numbers are not equal, or there will be a dead loop.

The 2nd solution is subtle: it actually does not swap numbers, but to change the signs of the index numbers. For example, if we found 1, then we set nums[0] to negative. Of course this will be affected by original negative numbers, thus there is a pre-processing to shield the negative numbers.

Solution 1:

# T:O(n) S:O(1)
class Solution:
    # @param A, a list of integers
    # @return an integer
    def firstMissingPositive(self, A):
        i = 0
        while i < len(A):
            if A[i] > 0 and A[i] - 1 < len(A) and A[i] != A[A[i]-1]:
                A[A[i]-1], A[i] = A[i], A[A[i]-1]
            else:
                i += 1
        
        for i, integer in enumerate(A):
            if integer != i + 1:
                return i + 1
        return len(A) + 1

Run Time: 52 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def firstMissingPositive(self, nums):
        length = len(nums)
        for i in xrange(length):
            if nums[i] <= 0:
                nums[i] = length + 2
        for i in xrange(length):
            if abs(nums[i]) <= length:
                ind = abs(nums[i]) - 1
                nums[ind] = - abs(nums[ind])
        for i in xrange(length):
            if nums[i] > 0:
                return i + 1
        return length + 1

Run Time: 76 ms