Very Easy Python Solution uses O(n) time and O(n) space. Think hashmaps!


class Solution:
# @param A : list of integers
# @return an integer
def firstMissingPositive(self, A):
n = len(A)
mp = {}
for i in range(0,n):
mp[A[i]] = i
maxval = max(A)
if maxval < 0:
return 1
for i in range(1,maxval):
if mp.get(i) is None:
return i
return (maxval+1)