Why is my code O(N^2) if there is only one for loop-CodePudding

I am trying to solve problem 4.1 on Codility.com. I need a solution which runs in O(N) time. My code solves the problem, but it runs in O(N^2) time, according to Codility's performance tests. Unfortunately I can't see why. There is only one for loop, which should scale linearly with n.

The challenge is to write a solution which tests whether an array ('A') contains all integers between 1 and X. It should return the index of the element which is the last element in 1 to X that appears in the array, or it should return -1 if not every integer between 1 and X is an element of the array. For example, the solution to X = 4 and A = [1, 3, 4, 2, 2] is 3 since 2 is the last element in 1 to 4 which appears in the array and it first appears in position 3. The solution to X = 5 and A = [1, 2, 4, 2, 3] is -1 because 5 never appears. My solution is below.

def Solution(X, A):
N = len(A)
count = [0] * (X   1)

# Solution for single-element arrays
if N == 1: 
    
    if A[0] == 1:
        return 0
    elif A[0] != 1:
        return - 1

# Solution for multi-element arrays
elif N != 1:
    
    for i in range(0, N   1, 1):
        if count[A[i]] == 0:
            count[A[i]] = count[A[i]]   1
        else:
            pass
        if count == [0]   [1] * (X):
            return i 
        elif count != [0]   [1] * (X) and i == N - 1: 
            return -1

Would anyone know why it runs in O(N^2) time? Codility's performance tests confirm this, but as far as I can see this should run in O(kN) time since there is only one for loop. Any help is appreciated.

CodePudding user response：

Something like this would work in O(n), you would have to adjust it to the exact question given:

def solution(x, a):
    
    b = []
    for v in a:
        # the conditions
        if (type(v) == int) and (v < x) and (v>1): b.append(v)
        else: return -1
            
    return b

# some examples

# this returns -1
a = [1,2,3,4,5.5,6]
x = solution(5,a)
print(x)


# this returns the the list [2, 3, 4]
a = [2,3,4]
x = solution(5,a)
print(x)

the reason why is because you can exit the list at the first fail with the return -1 statement.

CodePudding user response：

This should be O(N): a single instantiation of a list of length X, one for-loop over A which does O(1) retrieval of single list items, and one single final search of the list for None values.

def solution(X, A):
    pos = [None] * X
    for i, n in enumerate(A):
        if 1 <= n <= X:
            if pos[n-1] is None:
                pos[n-1] = i
    return pos[n-1] if None not in pos else -1

print(solution(4, [1, 3, 4, 2, 2]))
print(solution(5, [1, 2, 4, 2, 3]))
print(solution(1000, reversed(range(1, 1001))))

prints:

3
-1
999