Smallest Integer Problem Code Performance [duplicate]

Question

I am starting Python and I came across this practice test where I have to find the smallest positive integer that does not occur in a list.

Examples:

1. arr = [8, 2, 1, 4, 3, 5] # output: 6
2. arr = [-3, 1, 1, -7, 5, 3] # output: 2
3. arr = [-11, -1, 3] # output: 1

Here's my solution:

def solution(A):
    val = 1
    while True:
        try:
            idx = A.index(val)
            val += 1
        except ValueError:
            break
    return val

According to my results, I only got 1 out of the 4 performance tests. Could someone help me understand why?

Answer 1

You need to analyze time complexity to understand the bottle neck. Suppose K is the smallest integer you are looking for, and N is the length of your list. Then your code has complexity O(K*N), because for each iteration over K you are searching the list which takes O(N).

Now let's think about the best conceivable runtime (BCR). To find the integer you are inevitable (with a random list) need to iterate through the whole list, which is O(N). All the other parts might be dropped probably depending on the implementation. So our BCR = O(N). Most probably you need to target this time complexity to have all performance tests to pass.

Now to the solution. I don't think it's optimal, but it will definitely improve your version. You can convert list to the hashset. The search operation in hashset is O(1), so your solution will become O(K+N). The downside is that your space complexity will increase from O(1) to O(N)

def solution(A):
    B = set(A)
    val = 1
    while True:
        if val in B:
            val += 1
        else:
            break
    return val