Python / smallest positive integer

Question

I took following codility demo task Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].

My Solution

def solution(A):
    # write your code in Python 3.6
    l = len(A)
    B = []
    result = 0
    n = 0
    for i in range(l):
        if A[i] >=1:
            B.append(A[i]) 
    if B ==[]:
        return(1)
    else:    
       B.sort() 
       B = list(dict.fromkeys(B))
       n = len(B)
       for j in range(n-1):
           if B[j+1]>B[j]+1:
                result = (B[j]+1)
       if result != 0:
            return(result)
       else:
            return(B[n-1]+1)

Although I get correct output for all inputs I tried but my score was just 22%. Could somebody please highlight where I am going wrong.

Answer 1

Python solution with O(N) time complexity and O(N) space complexity:

def solution(A):
    arr = [0] * 1000001
    for a in A:
        if a>0:
            arr[a] = 1
    for i in range(1, 1000000+1):
        if arr[i] == 0:
            return i

My main idea was to:

1. creat a zero-initialized "buckets" for all the positive possibilities.
2. Iterate over A. Whenever you meet a positive number, mark it's bucket as visited (1).
3. Iterate over the "buckets" and return the first zero "bucket".

Answer 2

def solution(A):
    
    s = set(A)
    for x in range(1,100002):
        if x not in s:
            return x
    pass

And GOT 100%