LeetCode: 41. First Missing Positive

The essence of solving this problem within O(N) time complexity & O(1) memory is using the nums array itself as the hash for its numbers. That is, nums[i] should contain the information about whether i-1 is in nums or not.

Here, we should come up with an algorithm that marks nums array without messing up with the original value of nums[i]. Here, I accomplish such an algorithm using negative sign. An alternative would be using 'mod'.

class Solution:
     def firstMissingPositive(self, nums):
        n = len(nums)
        elem = None
        for i in range(n):
            if 1 <= nums[i] <= n:
                elem = nums[i]
                break
        if not elem:
            return 1              
        
        # nums[i] is for i-1
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = elem
        
        for num in nums:
            nums[abs(num)-1] = -abs(nums[abs(num)-1])
        
        for i, num in enumerate(nums):
            if num > 0:
                return i + 1
        return n + 1