# Python O(n) another approach, no swap

• the only three cases we have are:

1. missing a number k that k < len(nums)
2. missing len(nums)
3. missing len(nums)+1

so we first make every number in the list bigger than 0, then when we find each num in the list, we set nums[num] to be negative

if we find a number is not negative in index i, then we are missing number i,
or we are missing len(nums), simply check it,
or we are missing len(nums)+1

``````class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 1

# make every number positive
minN = min(nums)
comp = 0
if minN <= 0:
comp = abs(minN) + 1
for i in range(len(nums)):
nums[i] += comp

# set indexed number to negative
for i in range(len(nums)):
n = abs(nums[i])
if n - comp < len(nums) and n - comp >= 0:
if nums[n-comp] > 0:
nums[n-comp] = - nums[n-comp]

# find the first missing index and if len(nums) is in nums
l = len(nums) + comp
for i in range(1, len(nums)):
if nums[i] > 0:
return i
elif abs(nums[i]) == l: