Python2.x [EASY] [SETS]

class Solution:
# @param A : list of integers
# @return an integer
def firstMissingPositive(self, A):
    max_ = max(A)
    if max_ <= 0 :
        return 1
    else :
        for i in xrange(1,max_) :
            if i not in A :
                return i
        return max_ + 1


A beautiful and simple approach


Technically speaking, your solution isn’t O(n) since the number of searches made depends on max(A) which could be any large value. If an array contains large numbers, your solution won’t be accepted.


We know that the smallest missing positive number cannot be greater than len(A). So the answer has to be in [1, len(A)]. So instead of using max_ = max(A) in the for loop, you can simply use len(A), which will make your solution O(n) in time but again, we have to solve the problem in constant memory whereas your solution is O(n) in memory because of set(A).


bro,you won my heart .
i dont know what i was looking for , while such a simple and beautiful approach exist