```
class Solution:
# @param A, a list of integers
# @return an integer
def firstMissingPositive(self, A):
head,tail=0,len(A)-1
# reorder A to ensure the first head elements are positive number
while head<=tail:
if A[head]<=0 and A[tail]>0:
A[head],A[tail]=A[tail],A[head]
head,tail=head+1,tail-1
elif A[head]>0:
head+=1
elif A[tail]<=0:
tail-=1
# check each element and if the value is smaller than head, reverse the sign of the corresponding number at that index.
#The one that have not been reversed are element that are missing.
#And the first index would be the smallest integer that is missing.
for i in range(head):
if abs(A[i])<=head:
A[abs(A[i])-1]=-abs(A[abs(A[i])-1])
for i in range(head):
if A[i]>0:
return i+1
return head+1
```