```
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 1
n = len(nums)
a = [0] * (n+1)
a[0] = 1
for x in nums:
if x<=0 or x>n:
pass
else:
a[x] = 1
for i in range(n+1):
if not a[i]:
return i
return n+1
```

I know it may be not O(1) Space but it's still O(N) time. Leetcode can't import Bitarray so I used a list here to store 0,1. a[i] = 0 means positive integer i is not in the list.